> Quelques cours > Algorithmique et Analyse > 7. Tri par tas (Heapsort)

sommaire chapitre précédent

version imprimable

7. Tri par tas (Heap sort)

7.1. Principe

Le tri par tas1 est un tri par sélection : pour obtenir un tableau ordonné croissant, on recherche le plus grand élément du tableau non trié et on le place à sa position définitive qui est la dernière du tableau qui doit contenir les éléments triés, puis on réitère sur le tableau restant, et ainsi de suite...

La différence majeure avec le tri par sélection qui a été étudié au chapitre 2 vient de ce que le tableau à trier aura préalablement été organisé en tas pyramidal2.

7.2. Définitions

Dans ce qui suit on appelle tas (pyramidal) un arbre binaire parfait, partiellement ordonné c.-à-d. :

• un arbre (binaire) dont tous les niveaux sont complets, sauf le dernier, et sur le dernier niveau, les nœuds absents sont ceux de droite, (arbre parfait) :
• pour chaque nœud la valeur de clé vérifie (arbre partiellement ordonné) : clé (nœud) max (clé(fils_gauche), clé(fils_droit))

Exemple de tas pyramidal

• tous les niveaux sont complets sauf le dernier, les nœuds absents sont ceux de droite,
• pour chaque nœud on a clé (nœud) max (clé(fils_gauche), clé(fils_droit))

Les valeurs des clés (qui sont les mêmes que dans les exemples du chapitre 2) sont indiquées dans les boîtes rectangulaires. Les boîtes rondes contiennent des numéros qui sont les indices utilisées dans le cas d'un stockage (compact) de l'arbre binaire parfait dans un tableau.

Le fait que l'arbre soit partiellement ordonné entraîne que pour tout sous-arbre la valeur de la clé du nœud racine est supérieure ou égale aux valeurs des clés de tous les nœuds du sous-arbre (ce qui rend immédiate la recherche de l'élément le plus grand) ; par contre, à la différence de l'arbre binaire de recherche, il n'y a aucune relation entre les clés des nœuds d'un même niveau.

La structure d'arbre parfait permet un stockage compact dans un tableau : il suffit de stocker les clés de façon contiguë, rangée après rangée, de gauche à droite ; de cette façon, les indices des parents du nœud d'indice k sont aisément calculables (k/2 pour le père, 2k pour le fils gauche, 2k+1 pour le fils droit, si le premier élément est à l'indice 1). La hauteur de l'arbre à n nœuds est donc en O(log(n)).

7.3. Fonctions de la sélection

Il est illustré par le schéma ci-dessous : à chaque étape, il y a extraction du nœud racine puis reconstruction du tas pyramidal (on ne se préoccupe pas, pour l'instant, de savoir comment a été construit puis (re)construit le tas pyramidal).

Principe du fonctionnement de la sélection :

1. construire le tas pyramidal,
2. retirer l'élément du sommet de la pyramide, le ranger à la fin du tableau à garnir,
3. reconstruire le tas pyramidal, puis recommencer jusqu'à l'épuisement de l'arbre.

7.4. Comment recréer une structure pyramidale

On suppose qu'on a retiré la racine d'un tas pyramidal, le problème est de choisir dans l'arbre la clé qu'il faut mettre à la position racine pour recréer la structure de tas pyramidal (au moindre coût). Le schéma ci-dessous illustre la méthode (on remarquera que si l'abre a une profondeur p, il n'y a pas plus de p déplacements ou échanges) :

première idée :

Le nœud n°1 situé au sommet de la pyramide ayant été libéré, il est tentant de recréer la structure pyramidale en promouvant celui des deux fils qui porte la clé de plus forte valeur, puis de réitérer pour le nœud ainsi libéré jusqu'à atteindre une feuille ; ce qui est illustré par l'exemple ci-dessus :

La clé du nœud n°1 est remplacée par la clé du nœud n°2 qui à son tour est remplacée par la clé du nœud n°4 à laquelle on substitue la clé du nœud n°9, le nœud n°9 disparaît ; l'arbre résultant n'est plus parfait et on ne dispose pas de méthode simple pour rétablir cette propriété, c'est donc une mauvaise idée!

méthode définitive :

Le nœud n°1 situé au sommet ayant été libéré, on remplace sa clé par celle du nœud le plus en bas à droite de l'arbre (ici le nœud n°10) ; l'arbre est donc toujours parfait même s'il n'est plus partiellement ordonné ; pour rétablir cette dernière propriété il suffit, si nécessaire, de permuter la clé du sommet avec la plus forte clé de ses fils ; cette dernière opération sera ensuite appliquée au fils dont la clé a changé, et ainsi de suite...

Nous pouvons maintenant commencer à écrire l'algorithme. Mais d'abord, définissons le type "arbre binaire parfait" ; la définition du tableau où est stocké l'arbre n'a de sens que accompagnée des fonctions qui permettent de passer de tout nœud à son père et à ses fils.

Arbre binaire parfait (stockage implicite),
les expressions donnant les indices des nœuds dépendant de la borne inférieur k0 d'indiçage du tableau

En 7.3, nous avons vu, que nous avons besoin d'une procédure pour "re-pyramider" le sous-arbre, donnons-en d'abord les spécifications externes.

spécifications externes de la procédures "re-pyramider"

En 7.4, nous avons imaginé comment réaliser cette opération, l'écriture en est maintenant très simple :

principe de la procédure "re-pyramider" (formulation récursive)

Nous sommes en présence d'une récursion terminale, la transformation en algorithme itératif est aisée :

procédure "re-pyramider" (formulation itérative)

7.5. Construction de la pyramide

L'idée de base est très simple (comme lors de l'initialisation de l'algorithle de tri-fusion) : on part des pyramides pré-existantes, c.-à-d. à un seul nœud (autrement dit les nœuds feuilles) puis on re-pyramide tous les arbres dont la racine est père d'un nœud feuille, ensuite on re-pyramide les arbres pères de ceux préalablement pyramidés...

• on part d'un arbre parfait (non ordonné), on ordonne les nœuds des derniers derniers niveaux (ici les nœuds n°4 à 10) pour reconstruire des petites pyramides,
• puis on re-pyramide les sous-arbre dont les racines sont les nœuds du niveau immédiatement supérieur (ici les nœuds n°2 et 3), et on recommence pour les nœuds du niveau au dessus jusqu'à avoir atteint le nœud racine de l'arbre.

N.B. Pour faciliter la lecture du schéma, nous avons préféré ici re-pyramider par niveaux.

La procédure de construction de la pyramide initiale est la traduction immédiate de cette idée.

procédure "construire-pyramide"

7.6. Procédure de tri

La procédure est construite très simplement par assemblage des modules précédents, à chaque fois qu'on extrait le sommet de la pyramide on peut l'échanger, dans le même sous-tableau, avec le dernier élément puisque c'est ce dernier que l'on doit placer au sommet avant de re-pyramider (nous sommes donc en présence d'un tri "sur place" qui ne nécessite pas de tableau de travail annexe).

procédure Heapsort

7.7. Indice du père et des fils

Pour un tableau commençant à l'indice 1, les formules sont évidentes (pour toute autre valeur de k0, il sera prudent de faire des vérifications soigneuses...)

7.8. Compléxité

Bien que l'analyse paraisse complexe, on peut calculer dans tous les cas le nombre maximal de comparaisons et d'échanges : pour la construction de la pyramide initiale d'un tableau de n éléments, la complexité est en Θ(n), la complexité totale des opérations de re-pyramider après chaque extraction est en O(n log(n)). La complexité globale du tri est donc en O(n log(n)) et, à la différence de tri-fusion, il n'y a pas besoin de tableau de travail.

Nous sommes donc a priori en présence d'un algorithme très efficace. Cependant, si le tableau à trier est de grande taille, et si on travaille dans un système de mémoire virtuelle, les performances risquent d'être dégradées. En effet le parcours du tableau est guidé par l'examen du fils (ou du père) d'un nœud, ce qui fait passer de l'élément d'indice k à l'élément d'indice 2k (ou k/2) qui appartiennent le plus souvent à des pages différentes, ce qui peut entraîner de nombreux changements de page coûteux en durée d'exécution.

7.9. Exercice

Le programme suivant, écrit en FORTRAN 77, est extrait d'une bibliothèque connue. On prétend qu'il implémente l'algorithme Heapsort, est-ce exact?

version imprimable

retour vers le haut chapitre suivant