(** Le tri par tas **)


(* Rend une liste de n nombres aléatoires *)
random__init (int_of_float (sys__time()));;
let rec liste_aléat = function 
	|0 -> []
	|n -> (random__int 10000)::(liste_aléat (n-1))
;;

(* Fait un tri naïf de la liste *)
let rec insert_ds_liste_triée x liste = match liste with
	|[]   -> [x]
	|t::q -> if x<=t then x::liste
			     else t::(insert_ds_liste_triée x q)
;;

let rec tri_naif liste = match liste with
	|[]   -> []
	|[a]  -> [a]
	|t::q -> insert_ds_liste_triée t (tri_naif q)
;;

tri_naif [2;5;8;9;1;0;6];;
	
(* Début du tri par tas *)
type 'a Tas =
	|Rien
	|Noeud of 'a * 'a Tas * 'a Tas
;;

let racine = function
	|Rien		     -> failwith "Tas vide"
	|(Noeud (x,_,_)) -> x
;;

let rec enlever = function
	|Rien -> Rien
	|Noeud (x,Rien,fd) -> fd
	|Noeud (x,fg,Rien) -> fg
	|Noeud (_,fg,fd) -> let x=racine fg and y=racine fd in
		if x<y 
		then Noeud (x,enlever fg,fd)
		else Noeud (y,fg,enlever fd)
;;

let rec ajouter y untas = match untas with
	|Rien -> Noeud (y,Rien,Rien)
	|(Noeud (x,fg,fd)) -> 
		if x<y 
		then Noeud (x,fd,ajouter y fg)
		else Noeud (y,fd,ajouter x fg)
;;

let rec najouter liste untas = match liste with
	|[]	-> untas
	|t::q -> najouter q (ajouter t untas)
;;

let rec vider untas = match untas with
	|Rien -> []
	|tas  -> (racine tas)::(vider (enlever tas))
;;

let tripartas liste = vider (najouter liste Rien);;

(* Une petite comparaison *)
let liste = liste_aléat 1000;;
tri_naif liste;;
tripartas liste;;

(* Calcule la hauteur mini et maxi d'un tas *)
let rec hauteur tas = match tas with
	|Rien			 -> (0,0)
	|Noeud (x,fg,fd) -> let htg=hauteur fg and htd=hauteur fd in
					(1+(min (fst htg) (fst htd)),1+(max (snd htg) (snd htd)))
;;