Adloun

Insérer

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

Énoncé

Écrire insere et dérouler l'insertion de 0 dans le tas [| 1; 3; 2 |].

Corrigé

let insere t x =
  let d = t.donnees in
  d.(t.taille) <- x;
  t.taille <- t.taille + 1;
  let i = ref (t.taille - 1) in
  while !i > 0 && d.((!i - 1) / 2) > d.(!i) do
    let p = (!i - 1) / 2 in
    let tmp = d.(!i) in d.(!i) <- d.(p); d.(p) <- tmp;
    i := p
  done

On place 0 en indice 3 : [|1;3;2;0|]. Son parent (indice 1) est 3 &gt; 0 : on échange → [|1;0;2;3|]. Le nouveau parent (indice 0) est 1 &gt; 0 : on échange → [|0;1;2;3|]. 0 est remonté à la racine : c'est le nouveau minimum.

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.