Adloun

Construire un tas en

Exercice · OCaml (option informatique), chapitre 19 — Files de priorité : le tas binaire

Énoncé

On peut transformer un tableau quelconque en tas plus vite qu'en insérant un à un. Écrire construit d n qui réorganise d.(0..n-1) en tas par percolations vers le bas, des nœuds internes vers la racine.

Corrigé

let descendre d n i0 =       (* percoler le nœud i0 vers le bas dans d.(0..n-1) *)
  let i = ref i0 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 < n && d.(g) < d.(!petit) then petit := g;
    if dr < n && 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

let construit d n =
  for i = n / 2 - 1 downto 0 do descendre d n i done

On percole chaque nœud interne (indices n/2 - 1 à 0), des feuilles vers la racine : quand on traite i, ses sous-arbres sont déjà des tas. L'analyse fine donne un coût total (et non ). Remarque : OCaml propose downto ; si l'on s'en tient au seul to, on parcourt i de 0 à n/2-1 et l'on descend n/2 - 1 - i.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.