Tri par tas
Le tri par tas est un tri par sélection avec une meilleure façon de trouver la plus grande valeur. Il garde les valeurs non triées dans un tas, un arbre stocké dans la liste elle-même, où la plus grande valeur est toujours au sommet. La retirer et réparer le tas prend environ log n étapes au lieu d'un parcours complet.
Un arbre dans une liste
Un tas binaire est un arbre qui n'a pas besoin de pointeurs. La position 0 est la racine, et les enfants de la position i sont les positions 2i + 1 et 2i + 2 : les positions 1 et 2 sont donc les enfants de la racine, les positions 3 à 6 le niveau suivant, et ainsi de suite. Chaque niveau est plein sauf le dernier, qui se remplit par la gauche. Dans un tas max, chaque parent est au moins aussi grand que ses enfants, donc la plus grande valeur est toujours à la racine.
Faire descendre une valeur
Une seule opération fait tout le travail. Pour faire descendre (tamiser) une valeur, comparez-la à ses enfants. Si le plus grand enfant est plus grand que la valeur, ils s'échangent, et la valeur est comparée à ses nouveaux enfants. Elle s'arrête quand aucun enfant n'est plus grand, ou quand elle atteint le bas. Comme l'arbre n'a qu'environ log₂ n niveaux, une descente fait au plus environ 2 log₂ n comparaisons.
Construire le tas, puis trier
Pour construire le tas, faites descendre chaque parent, du dernier jusqu'à la racine. Chaque sous-arbre est un tas avant que son parent n'y descende. Puis triez : échangez la racine, la plus grande valeur, avec la dernière valeur du tas. Cette valeur est maintenant à sa place définitive. Le tas raccourcit d'une case, et la valeur arrivée à la racine descend pour le réparer. Recommencez jusqu'à ce qu'il ne reste qu'une valeur.
Un exemple
Prenons 5, 1, 4, 2, 8. La construction du tas fait descendre 1 sous 8, puis 5 sous 8, ce qui donne 8, 5, 4, 2, 1. Ensuite 8 passe à la fin ; 1 arrive à la racine et descend sous 5 et 2 : 5, 2, 4, 1 | 8. Puis 5 passe à la fin et 1 descend sous 4 : 4, 2, 1 | 5, 8. Deux tours de plus terminent la liste : 1, 2, 4, 5, 8, après 12 comparaisons et 10 échanges.
Forces et faiblesses
Le tri par tas prend un temps proportionnel à n log n même dans le pire cas, et il ne demande pas de mémoire supplémentaire. Le tri rapide peut ralentir jusqu'à n² et le tri fusion a besoin d'un tampon aussi long que la liste : le tri par tas est donc la solution de repli sûre. L'introsort, utilisé par la bibliothèque standard du C++, bascule sur lui quand les partitions du tri rapide tournent mal. Sur de vrais ordinateurs, il est généralement plus lent que les deux, car il saute entre des positions éloignées de la liste, et il n'est pas stable. J. W. J. Williams a publié le tri par tas, avec le tas binaire, en 1964.
À vous de jouer
Ouvrez l'application et appuyez sur Étape. L'arbre au-dessus des barres montre le tas : la valeur qui descend a sa propre couleur, l'enfant auquel elle est comparée est mis en évidence, et chaque échange apparaît à la fois dans l'arbre et dans les barres. Une fois le tas construit, regardez la racine passer à la fin, devenir verte et quitter l'arbre.
Questions fréquemment posées
Quelle est la complexité en temps du tri par tas ?
O(n log n) dans le meilleur cas, le cas moyen et le pire cas. Construire le tas prend O(n), et chacune des n − 1 extractions prend O(log n). Il trie en place avec O(1) de mémoire supplémentaire.
Quelle différence entre le tri par tas et le tri par sélection ?
Les deux prennent encore et encore la plus grande (ou la plus petite) valeur restante. Le tri par sélection la trouve en parcourant toute la partie non triée, soit n comparaisons à chaque fois. Le tri par tas garde la partie non triée dans un tas, où la plus grande valeur est déjà au sommet, et réparer le tas ne coûte qu'environ log n comparaisons.
À quoi sert un tas, à part trier ?
Aux files de priorité : un tas donne immédiatement le plus grand (ou le plus petit) élément et permet d'ajouter ou de retirer des éléments en environ log n étapes. Les ordonnanceurs, l'algorithme de plus court chemin de Dijkstra et les simulations à événements en utilisent tous un.
Le tri par tas est-il stable ?
Non. Échanger la racine avec la fin déplace les valeurs sur de longues distances, donc des valeurs égales peuvent changer d'ordre.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer le tri par tas