(* ===================================================== *) (* Apprentissage de la programmation avec OCaml *) (* Catherine Dubois & Valérie Ménissier-Morain *) (* Éditions Hermès Sciences *) (* Mars 2004 *) (* ===================================================== *) (* Fichier MLSRC/Tris_vecteurs/tri_tas.ml *) (* ===================================================== *)

type 'a tas = {tab: 'a array; mutable maximal: int};; let échanger t i j = let tmp = t.(i) in t.(i) <- t.(j); t.(j) <- tmp;; let fils_max t i = if 2*i+1>t.maximal then i else if 2*i+1=t.maximal || t.tab.(2*i+1) > t.tab.(2*i+2) then 2*i+1 else 2*i+2;; let rec réorganiser_descente_branche t i = if i = t.maximal then (* feuille *) () else let f = fils_max t i in if t.tab.(f) > t.tab.(i) then (échanger t.tab f i; réorganiser_descente_branche t f);; let supprimer_max_tas t = échanger t.tab 0 t.maximal; t.maximal <- t.maximal-1; réorganiser_descente_branche t 0;; let rec insérer_tas_tri t i = let père = (i-1)/2 in t.maximal <- t.maximal +1; if t.tab.(père) < t.tab.(i) then (échanger t.tab père i; insérer_tas_tri t père);; let tri_tas v = let t = {tab = v; maximal = 0} in let len = Array.length v - 1 in for i = 1 to len do insérer_tas_tri t i; done; for i = len downto 1 do supprimer_max_tas t; done;;