Implémentation et utilisation du tas binaire pour le tri par tas (Heapsort)

1. Maintenir la propriété de tas : Heapify

Imaginez un tas-max où un seul élément, à la racine, viole la propriété de tas. C'est-à-dire que cet élément est peut-être plus petit qu'un de ses enfants. Cependant, nous supposons que les sous-arbres gauche et droit de cette racine sont, eux, des tas-max valides.

Comment restaurer la propriété pour l'ensemble de l'arbre ? L'opération qui résout ce problème est Max-Heapify. Son principe est de faire "descendre" ou "percoler" l'élément fautif dans l'arbre jusqu'à ce qu'il trouve sa place.

La procédure est la suivante, pour un nœud à l'indice i :

1. On le compare à ses enfants gauche et droit.
2. Si un des enfants est plus grand que le parent, on identifie le plus grand des trois (le parent, le fils gauche, le fils droit).
3. Si le plus grand n'est pas le parent i, on échange i avec ce plus grand enfant.
4. Après l'échange, l'élément initialement à i se retrouve plus bas. Il est possible qu'il viole à nouveau la propriété de tas à sa nouvelle position. On répète donc l'opération récursivement sur le sous-arbre concerné.

La vidéo suivante, du cours d'algorithmique du MIT, détaille cette procédure max-heapify avec la rigueur attendue.

Remarque : Le professeur utilise une indexation à partir de 1. Comme nous l'avons vu, cela change légèrement les formules de calcul d'indices (parent = i/2, gauche = 2i, droit = 2i+1), mais le principe algorithmique reste identique.

2. Construire un tas : Build-Max-Heap

Maintenant que nous savons réparer un tas, comment en construire un à partir d'un tableau désordonné ?
L'idée est d'appliquer max-heapify de manière itérative. On considère le tableau comme un arbre binaire complet et on procède "de bas en haut".

L'algorithme Build-Max-Heap est le suivant :

1. On observe que tous les éléments de la seconde moitié du tableau sont des feuilles. Par définition, une feuille est un tas-max trivial de taille 1.
2. On parcourt donc les nœuds qui ne sont pas des feuilles, en partant du dernier (l'indice $\lfloor n/2\rfloor -1$ pour une indexation à 0) et en remontant jusqu'à la racine (indice 0).
3. Pour chacun de ces nœuds, on appelle max-heapify.

L'invariant de boucle garantit que lorsque max-heapify(i) est appelé, les sous-arbres de ses enfants sont déjà des tas-max valides, ce qui satisfait la précondition de l'opération.

Analyse de complexité de Build-Max-Heap

Une analyse simple donnerait : on appelle max-heapify environ $n/2$ fois, et chaque appel coûte $O(\log n)$. Le total serait donc $O(n\log n)$.

Cependant, une analyse plus fine, et c'est un point classique et important, montre que la complexité est en fait linéaire, soit $\Theta (n)$. L'intuition est que la plupart des appels à heapify se font sur des nœuds très bas dans l'arbre (des petits tas) et coûtent donc très peu, tandis que les appels coûteux (proches de la racine) sont rares.

La vidéo suivante propose une démonstration mathématique de ce résultat. C'est une analyse que vous devez maîtriser.

3. Le tri par tas : Heapsort

Armés de Build-Max-Heap et Max-Heapify, l'algorithme du tri par tas devient remarquablement simple.

L'algorithme Heapsort sur un tableau A de taille n se déroule comme suit :

1. Phase de construction : Appeler Build-Max-Heap(A). Le tableau est maintenant un tas-max, et l'élément le plus grand se trouve en A[0]. Coût : $\Theta (n)$.
2. Phase de tri : Itérer de i = n-1 à 1 :
   a. Échanger A[0] (le maximum actuel du tas) avec A[i]. L'élément maximum est maintenant à sa place finale dans le tableau trié.
   b. La taille du tas est virtuellement réduite de 1 (on ne considère plus l'élément à l'indice i).
   c. Le nouvel élément en A[0] peut violer la propriété de tas-max. Appeler Max-Heapify(A, 0) sur le tas réduit pour restaurer la propriété. Coût : $O(\log i)$.

Après $n-1$ itérations, le tableau est entièrement trié.

La complexité totale de Heapsort est la somme de la construction ($\Theta (n)$) et des $n-1$ extractions ($O(\log n)$ chacune). Le terme dominant est donc celui des extractions, ce qui donne une complexité totale de $\Theta (n\log n)$.

4. Implémentation en Python

Passons de la théorie à la pratique. Votre maîtrise du Python est un atout pour concrétiser ces algorithmes. Le document suivant vous fournit une implémentation claire et fonctionnelle de Heapsort.

Conclusion

Aujourd'hui, nous avons assemblé les pièces du puzzle pour construire un algorithme de tri des plus importants. Le tri par tas est un excellent exemple de la puissance d'une structure de données bien choisie.

Points clés à retenir :

• L'opération heapify (coût $O(\log n)$) est la procédure fondamentale pour maintenir la propriété de tas après une perturbation à la racine.
• L'algorithme build-heap transforme un tableau quelconque en un tas en temps linéaire ($O(n)$), un résultat non-intuitif mais crucial.
• Heapsort utilise build-heap une fois, puis extrait itérativement le maximum en appelant heapify à chaque étape, aboutissant à une complexité garantie de $\Theta (n\log n)$.
• C'est un tri en place, ce qui le rend très efficace en termes d'utilisation mémoire.

Prochaine étape :
Nous avons maintenant exploré plusieurs algorithmes de tri basés sur des comparaisons (insertion, fusion, rapide, par tas). La prochaine leçon brisera ce paradigme. Nous aborderons le tri par comptage (counting sort) et le tri par base (radix sort), des algorithmes qui, sous certaines hypothèses sur les données d'entrée, peuvent trier en temps linéaire et ainsi battre la borne inférieure de $\Omega (n\log n)$ des tris par comparaison.