Kha-tastrophe.net

Le site kha-tastrophique de Kha

> Cours > Informatique> Algorithmique et Analyse > Tri par tas (Heapsort)

7. Tri par tas (Heapsort)

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...

1. Imaginé par J. W. J. Williams : Algorithm 232, Communication of the ACM, 1964.

fermer cette précision

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.

2. On peut préférer le mot "pyramide" au mot "tas" car, à la différence de pyramide, le mot tas n'évoque qu'un objet inorganisé ce qui est loin de la structure que nous allons décrire. Certes il semble avéré que la première apparition du mot tas a été liée à l'algorithme que nous étudions, cependant l'usage actuel, qui est d'utiliser tas pour désigner la zone de mémoire où sont allouées "en vrac" les espaces requis par un processus d'allocation dynamique, nous semble plus approprié.

fermer cette précision

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) Symbole : supérieur et égal max (clé(fils_gauche), clé(fils_droit))

Exemple de tas pyramidal

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) Symbole : supérieur et égal 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 :

Schéma illustrant le 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 :

Première idée pour recréer une structure pyramidale

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 :

méthode définitive pour recréer une structure pyramidale

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...

Renouveller la racine
Les flèches bordeaux simples montrent les déplacements des clés et les flèches doubles les échanges.
La flèche rouge montre le déplacement de la clé du dernier nœud vers la racine.
On a marqué en noir le nœud qui, au terme des opérations, a été vidé.

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

TYPE
    ty_arbre_binaire_parfait = tableau de "valeur_clé" indice (k0..???)
    
    /* fonctions calculant, pour un arbre binaire parfait, les indices des noeuds associés au noeud d'indice k */
    
    Fonction indice_fils_gauche(k)
    
    Fonction indice_fils_droit(k)
    
    Fonction indice_père(k)

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"

Procédure re_pyramider (T : ty_arbre_binaire_parfait, Entrée/Sortie;
                        k_top : indice pour T, Entrée /* racine du sous-arbre à re-pyramider */
                        k_last : indice pour T, entrée /* dernier élément de l'arbre */ )
/* re_pyramider "ré-ordonne partiellement" le sous-arbre dont la racine est à l'indice "k_top"
    on suppose que sont déjà "partiellement ordonnés" les sous-arbres de racines :
    T(fils_gauche(k_top)) et T(fils_droit(k_top)) */

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)

    déterminer k_max = indice du noeud de clé maximale (T(k_top)),
    /* et, (si ces noeuds existent) */ T(fils_gauche(k_top), T(fils_droit(k_top)) )
    
    si k_max Symbole : différent k_top alors
        échanger (k_top), T(k_max))
        re_pyramider (T, k_max, k_last)      récursion "terminale"
    sinon       /* le sous-arbre dont la racine est à l'indice "k_top" est déjà "partiellement ordonné" */
    fin_si
fin_procédure re_pyramider

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)

Procédure re_pyramider (T : ty_arbre_binaire_parfait, Entrée/Sortie;
                        k_top : indice pour T, Entrée /* racine du sous-arbre à re-pyramider */
                        k_last : indice pour T, entrée /* dernier élément de l'arbre */ )

/* re_pyramider "ré-ordonne partiellement" le sous-arbre dont la racine est à l'indice "k_top"
    on suppose que sont déjà "partiellement ordonnés" les sous-arbres de racines :
    T(fils_gauche(k_top)) et T(fils_droit(k_top)) */
    
    variables locales k, kg, kd, k_max : indices pour T
    k Symbole : affectation k_top    k pointe, à chaque itération, vers la racine du sous-arbre qu'il faut (éventuellement) re-pyramider
    répéter
        tant que indice_fils_gauche(k) Symbole : inférieur et égal k_last     car s'il n'y a qu'un fils, c'est le gauche!
            k_max Symbole : affectation k
            kg Symbole : affectation indice_fils_gauche(k)
            si T(kg) > T(k_max) alors
                k_max Symbole : affectation kg
            fin_si
            kd Symbole : affectation indice_fils_droit(k)
            si kd Symbole : inférieur et égal k_last alors
                si T(kd) > T(k_max) alors
                    k_max Symbole : affectation kd
                fin_si
            fin_si
            
            si k_max Symbole : différent k alors
                échanger (T(k), T(k_max))
                k Symbole : affectation k_max
            sinon
                cesser_de_répéter     car le sous-arbre de racine "k" est déjà "partiellement ordonné"
            fin_si
    fin_répéter
fin_procédure re_pyramider

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...

Construction de la pyramide

Première étape

Schéma illustrant la première étape de la procédure re-pyramider

Etape suivante

Schéma illustrant l'étape suivante de la procédure re-pyramider

Pyramide achevée

Schéma illustrant la pyramide achevée après la procédure re-pyramider

  • 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"

Procédure construire_pyramide (T : ty_arbre_binaire_parfait, Entrée/Sortie;
                               k_last : indice pour T, Entrée /* dernier élément de l'arbre */ )
    /* construire_pyramide rend l'abre de racine T(k0) "partiellement ordonné" */
    variable locale k : indice pour arbre_binaire_parfait
    répéter
        pour k décroissant de indice_père(k_last) à k0
            re_pyramider(T, k, k_last)
    fin_répéter
fin_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

Procédure Heap_sort (T : ty_arbre_binaire_parfait, Entrée/Sortie;
                     Nb_T : indice pour T, Entrée /* indice du dernier élément du tableau T */ )
    variable locale n : indice pour T
    /* indice du dernier élément du sous-tableau restant à trier */
    
    construire pyramide(T, Nb_T)
    
    répérer
        pour n décroissant de Nb_T à k0+1
            échanger (t(k0), T(n))
            re_pyramider (T, k0, n-1)
    fin_répéter
fin_Procédure Heap_sort

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...)

TYPE
    arbre_binaire_parfait = tableau de "valeur_clé" indicé (1..???)

Fonction indice_fils_gauche (k)
    indice_fils_gauche Symbole : affectation 2 * k
fin_Fonction indice_fils_gauche

Fonction indice_fils_droit (k)
    indice_fils_droit Symbole : affectation 2 * k + 1
fin_Fonction indice_fils_droit

Fonction indice_père (k)
    indice_père Symbole : affectation partie entière (k / 2)
fin_Fonction indice_père

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?

    SUBROUTINE SORT(N,RA)
*       sorts an array RA of length N into ascending numérical order
*       using the HEAPSORT algorithm
*       N is input
*       Ra is replaced on output by its sorted rearrangement.
        DIMENSION RA
        L=N/2+1
        IR=N
10      CONTINUE
            IF (L.GT.1) THEN
                L=L-1
                RRA=RA(L)
            ELSE
                RRA=RA(IR)
                RA(IR)=RA(1)
                IR=IR-1
                IF (IR.EQ.1) THEN
                    RA(1)=RRA
                    RETURN
                ENDIF
            ENDIF
            I=L
            J=L+L
20          IF (J.LE.IR) THEN
                IF (J.LT.IR) THEN
                    IF (RA(J).LT.RA(J+1)) J=J+1
                ENDIF
                IF (RRA.LT.RA(J)) THEN
                    RA(I)=RA(J)
                    I=J
                    J=J+J
                ELSE
                    J=IR+1
                ENDIF
                GO TO 20
            ENDIF
            RA(I)=RRA
            GO TO 10
        END