Tas binaire : une file de priorité dans un tableau

Quinze clés occupent un tableau qui représente aussi un arbre : les deux enfants de la position i se trouvent aux positions 2i + 1 et 2i + 2. Construisez un tas par insertions successives ou en partant du dernier parent. Suivez chaque comparaison et chaque échange, puis extrayez la plus petite clé : la suivante prend sa place.

Exemple résolu — Tas binaire : une file de priorité dans un tableau

Clés	15
Construction par insertions successives	34 comparaisons, 34 échanges
Construction depuis le dernier parent	22 comparaisons, 11 échanges

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Tas binaire : une file de priorité dans un tableau

Un tas binaire min est un tableau où la clé à chaque position i est inférieure ou égale aux clés situées aux positions 2i + 1 et 2i + 2, ses enfants. Le parent de la position i se trouve à la position ⌊(i − 1) / 2⌋. Ainsi lu, le tableau représente un arbre binaire complet. La plus petite clé est toujours à la position 0, la racine. Pour insérer une clé, placez-la à la fin du tableau et faites-la remonter : échangez-la avec son parent tant qu’elle lui est inférieure. Pour extraire la plus petite clé, déplacez la dernière clé à la racine et faites-la descendre : échangez-la avec son plus petit enfant tant que celui-ci lui est inférieur. Un tas utilisé de cette façon constitue une file de priorité.

Ce que signifie chaque symbole

n: le nombre de clés dans le tas
i: une position dans le tableau, numérotée à partir de 0
h: la hauteur d’une position : le nombre de niveaux situés en dessous, ⌊log₂(n / (i + 1))⌋

Suppose: Une comparaison confronte deux clés ; un échange permute les clés de deux positions. Déplacer la dernière clé à la racine lors d’une extraction ne compte ni comme une comparaison ni comme un échange. Une clé égale à son parent ou à son plus petit enfant reste en place. Si les deux enfants sont égaux, on choisit celui de gauche. Le tas garde la plus petite clé à la racine ; pour un tas max, il suffit d’inverser toutes les comparaisons. L’outil accepte jusqu’à quinze clés de 0 à 99, afin que l’arbre entier tienne sur l’écran d’un téléphone. Les permutations comptées dans la dernière ligne portent sur des clés distinctes.

Les insertions successives coûtent selon la profondeur, la construction depuis le dernier parent selon la hauteur 🖖

Cliquez sur Décroissant, un à un. Chaque nouvelle clé est inférieure à toutes celles du tas. Elle remonte jusqu’à la racine, avec 1 comparaison et 1 échange par niveau : 0 pour la racine, 1 pour chacune des 2 positions suivantes, 2 pour chacune des 4 suivantes, 3 pour chacune des 8 dernières. Le total est de 34. Cliquez maintenant sur Décroissant, par le bas. Les mêmes 15 clés sont placées dans leur ordre d’arrivée, puis on fait descendre la clé de chaque position ayant des enfants, de 6 à 0. Une clé ne peut descendre que du nombre de niveaux situés sous elle. Or, 8 des 15 positions sont des feuilles : rien ne se trouve en dessous. Ces positions, qui coûtaient chacune 3 niveaux avec la première méthode, ne coûtent rien ici. La somme des hauteurs vaut 11 ; à raison de 2 comparaisons par niveau, on obtient 22. Dans tout tas, la somme des hauteurs vaut n moins le nombre de chiffres 1 dans l’écriture binaire de n. Cette construction demande donc toujours moins de 2n comparaisons. Avec 1 023 clés présentées par ordre décroissant, les deux méthodes en demandent respectivement 8 194 et 2 026.

Dans l’ordre croissant, les deux constructions demandent les mêmes 14 comparaisons 🖖

Cliquez sur Croissant, un à un. Chaque nouvelle clé est déjà supérieure ou égale à son parent : 1 comparaison, aucun échange, soit 14 comparaisons au total. Passez à À partir du dernier parent : le total reste de 14. Chaque parent compare ses deux enfants, puis se compare au plus petit, et s’arrête là. Pour les deux méthodes, 14 est le minimum : toute clé sauf la racine doit être comparée au moins une fois. Au-delà, les coûts divergent. L’ordre décroissant porte les insertions successives à leur maximum, tandis qu’un ordre aléatoire donne des résultats bien plus proches du minimum. Sur 200 mélanges de 1 000 clés, les insertions successives ont demandé en moyenne 2 235 comparaisons, et la construction depuis le dernier parent 1 862, contre 7 987 pour les insertions des mêmes clés dans l’ordre décroissant. Avec 15 clés, l’écart est faible : cliquez plusieurs fois sur Mélanger, et les insertions successives l’emporteront de temps à autre.

Un tas est encore loin d’être trié 🖖

Un tas garantit que chaque clé est inférieure ou égale à celles de ses enfants. Parmi les 5 040 permutations de 7 clés distinctes, 80 respectent cette condition. La plus petite doit être à la racine ; n’importe quel groupe de 3 clés parmi les 6 autres peut occuper le sous-arbre gauche, et chaque sous-arbre doit lui-même être un tas. Le nombre de tas vaut ainsi 7! divisé par le produit des tailles de tous les sous-arbres, soit 7 · 3 · 3. Pour 15 clés, le tableau des résultats indique 21 964 800 tas parmi 1 307 674 368 000 permutations. Une seule est triée. Cette liberté explique le faible coût de construction d’un tas. L’ordre se révèle au fil des extractions : cliquez sur Tri par tas. À chaque extraction de la racine, la dernière clé prend sa place, puis descend. La plus petite clé restante rejoint alors la racine. Les 12 clés sortent dans l’ordre : 3, 7, 12, et ainsi de suite jusqu’à 93.

Problème entièrement résolu

Combien de comparaisons faut-il pour chaque construction avec un millier de clés ? 4 étapes
Cliquez sur Décroissant, un à un, puis sur Décroissant, par le bas, et expliquez les totaux de 34 et 22. Prenez ensuite 1 023 clés présentées par ordre décroissant. Combien de comparaisons chaque méthode effectue-t-elle ?

Ouvrez ce problème dans l'outil
1. La position i se trouve à la profondeur ⌊log₂(i + 1)⌋ : 1 position à la profondeur 0, 2 à la profondeur 1, 4 à la profondeur 2 et 8 à la profondeur 3. Dans l’ordre décroissant, chaque nouvelle clé est la plus petite reçue jusque-là. Elle remonte jusqu’à la racine, avec 1 comparaison et 1 échange par niveau : 0 + 2 · 1 + 4 · 2 + 8 · 3 = 34.
  
  $0 + 2 \cdot 1 + 4 \cdot 2 + 8 \cdot 3 = 34$
2. En partant du dernier parent, c’est la hauteur qui compte : 3 pour la racine, 2 pour les positions 1 et 2, 1 pour les 4 positions à la profondeur 2, 0 pour les 8 feuilles, soit 11 au total. Dans l’ordre décroissant, chaque clé descend jusqu’à une feuille. Avec 15 clés, chaque parent a deux enfants ; chaque niveau demande donc 2 comparaisons. On obtient 22 comparaisons et 11 échanges.
  
  $3 + 2 \cdot 2 + 4 \cdot 1 = 11, 2 \times 11 = 22$
3. Avec 1 023 = 2¹⁰ − 1 clés, tous les niveaux de l’arbre sont remplis : il y en a 10, avec 2ᵈ positions à la profondeur d. Le coût des insertions successives est la somme des profondeurs : 1 · 2 + 2 · 4 + 3 · 8 + ⋯ + 9 · 512 = 8 194 comparaisons, et autant d’échanges.
  
  $d = 0 \sum 9 d \cdot 2^{d} = 8 \cdot 2^{10} + 2 = 8194$
4. La construction depuis le dernier parent coûte le double de la somme des hauteurs. Il y a 2⁹ positions de hauteur 0, 2⁸ de hauteur 1, et ainsi de suite jusqu’à la racine, de hauteur 9 : 1 · 256 + 2 · 128 + ⋯ + 9 · 1 = 1 013. C’est aussi 1 023 moins les 10 chiffres 1 de son écriture binaire. Le double donne 2 026 comparaisons, pour 1 013 échanges.
  
  $h = 0 \sum 9 h \cdot 2^{9 - h} = 1023 - 10 = 1013, 2 \times 1013 = 2026$
Réponse

8 194 comparaisons par insertions successives, 2 026 depuis le dernier parent, soit environ 8 par clé contre 2. La plupart des positions d’un tas ont une grande profondeur et une faible hauteur. L’insertion coûte selon la profondeur ; la construction depuis le dernier parent, selon la hauteur. L’outil s’arrête à 15 clés : le même calcul donne alors les totaux de 34 et 22 qu’il affiche.

$8194 against 2026$

Parcours

Ce qu’une structure de données rend peu coûteux

Références (2)

Heapsort as first published: J. W. J. Williams, "Algorithm 232: Heapsort," Communications of the ACM 7(6), 347–348, June 1964.
The heap-based sort published six months later, close to the version used today: Robert W. Floyd, "Algorithm 245: Treesort 3," Communications of the ACM 7(12), 701, December 1964.

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.