Extraire le minimum

let extrait_min t =
  if est_vide t then failwith "tas vide";
  let d = t.donnees in
  let mini = d.(0) in
  t.taille <- t.taille - 1;
  d.(0) <- d.(t.taille);
  let i = ref 0 and continuer = ref true in
  while !continuer do
    let g = 2 * !i + 1 and dr = 2 * !i + 2 in
    let petit = ref !i in
    if g < t.taille && d.(g) < d.(!petit) then petit := g;
    if dr < t.taille && d.(dr) < d.(!petit) then petit := dr;
    if !petit <> !i then begin
      let tmp = d.(!i) in d.(!i) <- d.(!petit); d.(!petit) <- tmp; i := !petit
    end
    else continuer := false
  done;
  mini

On renvoie la racine, on y remonte la dernière feuille, puis on la fait redescendre vers le plus petit enfant tant qu'elle est trop grande. Les tests g < t.taille et dr < t.taille vérifient l'existence des enfants.