(* Exercice 1 *)

let pere i=(i+1)/2-1 and fg i=2*i+1 and fd i=2*(i+1);;

let heap v=let n=vect_length v
	and swap i j=let x=v.(i) in
		begin v.(i)<-v.(j); v.(j)<-x end in
	let build_again i=let j=ref i in
		while (!j>0) & (v.(pere !j)>v.(!j)) do
			swap !j (pere !j); j:=(pere !j); done;
	and sort i=let j=ref 0 and k=ref 0 in
		begin
			swap (n-i-1) 0;
			while (fg !j)<=(n-2-i) do (*on s'arrete aux feuilles*)
				if ((fg !j)=n-2-i)||(v.(fg !j)<v.(fd !j))
					then k:=fg !j else k:=fd !j;
				if v.(!j)>v.(!k) then (swap !j !k; j:= !k)  else j:=n
			done
		end
	in
	for k=1 to (n-1) do build_again k done;
	for k=0 to (n-2) do sort k done;
	v;;
(*heap : 'a vect -> 'a vect = <fun>*)

heap [|3;8;6;9;7;1;2;5;10;4|];;
(*- : int vect = [|10; 9; 8; 7; 6; 5; 4; 3; 2; 1|]*)


let heap2 v=let n=vect_length v   (*constitution linéaire du tas*)
	and swap i j=let x=v.(i) in
		begin v.(i)<-v.(j); v.(j)<-x end in
	let percole i t= (* t=dernier élément du tas *)
	  let j=ref i and k=ref 0 in
		while (fg !j)<=t (*on s'arrète aux feuilles*)
		  do if (fg !j)=t||(v.(fg !j)<v.(fd !j))
					then k:=fg !j else k:=fd !j;
			 if v.(!j)>v.(!k) then
					begin swap !j !k; j:= !k end else j:=n
		  done
	in let  sort i=begin swap (n-1-i) 0; percole 0 (n-2-i) end
	in
	for k=(pere (n-1)) downto 0 do percole k (n-1) done;
	for k=0 to (n-2) do sort k done;
	v;;

(*heap2 : 'a vect -> 'a vect = <fun>*)

heap2 [|3;8;6;9;7;1;2;5;10;4|];;
(*- : int vect = [|10; 9; 8; 7; 6; 5; 4; 3; 2; 1|]*)


(* Exercice 2 *)

(*
Naif : on trie le tableau globalement puis on ne prend que les n^(4/5) plus gros éléments.
Ca coute Omega(nln n)...

Futé : On constitue le tas global en O(n) comparaisons,
puis on classe les éléments qui nous intéressent en O(n^(4/5)ln(n^(4/5))),
ce qui est bien un O(n)... *)


(* Exercice 3 *)

(* fg(i)=3i+1, fc(i)=3i+2 et fd(i)=3i+3, puis pere(i)=(i-1)/3...
dans la phase de tri, le nb d'échanges est <= nln n/ln 3 + K, ce qui est mieux que 
pour un tas binaire, mais chaque étape nécessite jusqu'à trois comparaisons, contrairement
à 2 pour les tas binaires. *)


(* Exercice 4 *)


type arbre=V|F of int|N of arbre*int*arbre;;

type 'a pile==('a list) ref;;
let Pile_vide ()= (ref [])
and push x (p:'a pile)=(p:=x:: !p)
and pop (l:'a pile)=let x=hd !l in l:=tl !l;x
and est_vide (l:'a pile)=(!l=[]);;

(* NB : il ne faut pas utiliser l'implémentation particulière de ces piles
pour être honnète *)

let rec empile a p=match a with
  | V -> ()
  | F(x) -> push x p
  | N(g,x,d) -> empile g p; push x p; empile d p;;

let tri_ABR a=let p=Pile_vide ()  and l=ref [] in
  empile a p;
  while not (est_vide p) do l:=(pop p)::(!l) done;
  !l;;


tri_ABR (N(N(V,5,N(F(6),7,F(8))),10,N(F(12),15,N(F(16),19,F(30)))));;
(*- : int list = [5; 6; 7; 8; 10; 12; 15; 16; 19; 30]*)

(* Le professeur Duchmule est un escroc : s'il pouvait constituer l'ABR en O(n)
comparaisons, on pourrait trier en O(n) comparaisons, or on sait que c'est impossible...*)



(* Exercice 5 *)

(* insert(x::l3) a pour racine x, et ses fils sont insert(l1) et insert(l2). Le résultat
est donc le même quelque soit le mélange de l1 et l2. On en déduit sans trop de mal
que le nombre de façons d'obtenir l'arbre de l'exercice est C_13^9N_1N_2, avec
N_1=C_8^3N_11N_12 avec N_11=1 et N_12=C_4^2, et enfin N_2=C_3^1.

Pour obtenir un arbre de hauteur 13, lle début de la liste doit être le plus petit ou le
plus grand; le suivant doit être le plus petit ou le plus grand de ce qui reste, etc...
Au total, on a donc 2^13 possibilités. *)