OCaml (option informatique) · Chapitre 19 · Application directe du cours

Naviguer dans le tableau

Files de priorité : le tas binaire · niveau 1 (application)

Énoncé

Donner les indices du parent, du fils gauche et du fils droit du nœud 4. Dessiner l'arbre du tableau [| 1; 3; 2; 7; 5 |] et vérifier que c'est un tas.

Corrigé

Parent de 4 : (4-1)/2 = 1 ; fils gauche : 2*4+1 = 9 ; fils droit : 10. Pour [|1;3;2;7;5|] : racine 1, enfants 3 et 2 ; enfants de 3 (indice 1) : 7 et 5. Chaque nœud est $\leq$ ses enfants ( $1 \leq 3, 2$ ; $3 \leq 7, 5$ ) : c'est bien un tas, de minimum 1.

Exercices semblables

Construire un tas en $Θ (n)$ corrigé
File de priorité de couples corrigé
Dijkstra avec file de priorité corrigé
API de base corrigé
Insérer corrigé

Le cours du chapitre · Tous les exercices du chapitre