Un tas est appelé 'partiellement ordonné' et non 'partiellement trié'. Le mot 'trier' signifie ordre complet (tri complet). Un tas n'est pas partiellement ordonné arbitrairement. Un tas est partiellement ordonné selon un critère (modèle), comme indiqué ci-dessous.
Ainsi, le tri en tas se compose de deux étapes : la construction du tas et l'extraction de l'élément ordonné du haut du tas. Dans la deuxième étape, après chaque extraction, le tas est reconstruit. Chaque reconstruction est plus rapide que le processus de construction d'origine puisque la reconstruction est effectuée à partir d'une version précédente, où un élément a été supprimé. Et avec cela, heapsort trie une liste complètement non triée.
Le but de cet article est d'expliquer brièvement le tri en tas puis de produire sa complexité temporelle (voir la signification de la complexité temporelle ci-dessous). Vers la fin, le codage se fait en C++.
Tas minimal
Un tas peut être un tas minimum ou un tas maximum. Un max-heap est celui où le premier élément est l'élément le plus élevé, et l'arbre entier ou la liste correspondante est partiellement ordonné par ordre décroissant. Un min-heap est celui où le premier élément est le plus petit élément, et toute la liste est partiellement ordonnée par ordre croissant. Dans cet article, seul le tas minimum est pris en compte. Remarque : dans le sujet du tas, un élément est aussi appelé nœud.
Un tas est un arbre binaire complet. L'arbre binaire peut être exprimé sous la forme d'un tableau (liste) ; lire de haut en bas et de gauche à droite. La propriété de tas pour un min-heap est qu'un nœud parent est inférieur ou égal à chacun de ses deux enfants. Un exemple de liste non ordonnée est :
| 9 | 19 | 24 | 5 | 3 | Onze | 14 | 22 | sept | 6 | 17 | quinze | nul | nul | nul |
| 0 | 1 | deux | 3 | 4 | 5 | 6 | sept | 8 | 9 | dix | Onze | 12 | 13 | 14 |
La première ligne de ce tableau est les éléments du tableau. Dans la deuxième ligne se trouvent les index de base zéro. Cette liste d'éléments peut être exprimée sous forme d'arbre. Les éléments nuls ont été ajoutés pour créer un arbre binaire complet. Strictement parlant, les éléments nuls ne font pas partie de la liste (arbre). Cette liste n'a pas d'ordre, donc ce n'est pas encore un tas. Il deviendra un tas lorsqu'il aura eu un ordre partiel, selon la propriété du tas.
Relation entre les nœuds et les index
Rappelez-vous qu'un tas est un arbre binaire complet avant d'avoir la configuration du tas (propriété du tas). La liste précédente n'est pas encore un tas, car les éléments n'obéissent pas à la propriété tas. Il devient un tas après avoir réorganisé les éléments dans un ordre partiel selon la propriété min-heap. L'ordre partiel peut être considéré comme un tri partiel (bien que le mot 'tri' signifie un ordre complet).
Qu'un arbre binaire soit un tas ou non, chaque parent a deux enfants, à l'exception des nœuds feuilles (derniers). Il existe une relation mathématique entre les indices entre chaque parent et ses enfants. C'est comme suit : Si le parent est à l'index i, alors l'enfant de gauche est à l'index :
deux * je + 1et le bon enfant est à l'index :
deux * je + deuxC'est pour l'indexation de base zéro. Ainsi, un parent à l'indice 0 a son enfant gauche à l'indice 2×0+1=1 et son enfant droit à 2×0+2=2. Un parent à l'index 1 a son enfant gauche à l'index 2×1+1=3 et son enfant droit à l'index 2×1+2=4 ; etc.
Par la propriété min-heap, un parent à i est inférieur ou égal à l'enfant gauche à 2i+1 et inférieur ou égal à l'enfant droit à 2i+2.
Tas
Entailler signifie construire un tas. Cela signifie réorganiser les éléments d'une liste (ou de l'arbre correspondant) afin qu'ils satisfassent la propriété du tas. À la fin du processus d'entassement, la liste ou l'arbre est un tas.
Si la liste non triée précédente est entassée, elle deviendra :
| 3 | 5 | Onze | sept | 6 | quinze | 14 | 22 | 9 | 19 | 17 | 24 | nul | nul | nul |
| 0 | 1 | deux | 3 | 4 | 5 | 6 | sept | 8 | 9 | dix | Onze | 12 | 13 | 14 |
Remarque : il y a 12 éléments et non 15 dans la liste. Dans la deuxième ligne se trouvent les index. Dans le processus de construction du tas, les éléments devaient être vérifiés et certains échangés.
Notez que le plus petit et le premier élément est 3. Le reste des éléments suit de manière ascendante mais ondulante. Si les enfants gauche et droit aux positions 2i+1 et 2i+2 sont chacun supérieurs ou égaux au parent en i, alors il s'agit d'un tas min. Il ne s'agit pas d'une commande ou d'un tri complet. Il s'agit d'un ordre partiel, selon la propriété du tas. C'est à partir de là que commence la prochaine étape du tri par tas.
Heapifier la complexité temporelle
La complexité temporelle est le temps d'exécution relatif d'un code. Il peut être considéré comme le nombre d'opérations principales que ce code doit effectuer. Il existe différents algorithmes pour la construction de tas. Les plus efficaces et les plus rapides divisent continuellement la liste par deux, en vérifiant les éléments à partir du bas, puis en faisant quelques échanges d'éléments. Soit N le nombre d'éléments pratiques dans la liste. Avec cet algorithme, le nombre maximal d'opérations principales (permutation) est N. La complexité temporelle pour l'entassement est donnée auparavant par :
O ( n )Où n est N et est le nombre maximal possible d'opérations principales. Cette notation s'appelle la notation Big-O. Il commence par O en majuscule, suivi de parenthèses. À l'intérieur des parenthèses se trouve l'expression du plus grand nombre possible d'opérations.
N'oubliez pas : l'addition peut devenir une multiplication si la même chose ajoutée se répète.
Illustration de tri en tas
La liste non triée précédente sera utilisée pour illustrer le tri en tas. La liste donnée est :
9 19 24 5 3 Onze 14 22 sept 6 17 quinzeLe tas min produit à partir de la liste est :
3 5 Onze sept 6 quinze 14 22 9 19 17 24La première étape du tri en tas consiste à produire le tas qui a été produit. Ceci est une liste partiellement ordonnée. Ce n'est pas une liste triée (complètement triée).
La deuxième étape consiste à supprimer le plus petit élément, qui est le premier élément, du tas, à réempiler le tas restant et à supprimer le moins d'éléments dans les résultats. Le plus petit élément est toujours le premier élément du tas ré-entassé. Les éléments ne sont pas enlevés et jetés. Ils peuvent être envoyés à une baie différente dans l'ordre dans lequel ils sont supprimés.
Au final, le nouveau tableau aurait tous les éléments triés (complètement), par ordre croissant ; et non plus seulement partiellement commandé.
Dans la deuxième étape, la première chose à faire est d'enlever 3 et de le placer dans le nouveau tableau. Les résultats sont :
3et
5 Onze sept 6 quinze 14 22 9 19 17 24Les éléments restants doivent être entassés avant que le premier élément ne soit extrait. Le tas des éléments restants peut devenir :
5 6 sept 9 quinze 14 22 Onze 19 17 24Extraire 5 et ajouter à la nouvelle liste (tableau) donne les résultats :
3 5et
6 sept 9 quinze 14 22 Onze 19 17 24L'entassement de l'ensemble restant donnerait :
6 sept 9 quinze 14 22 Onze 19 17 24Extraire 6 et ajouter à la nouvelle liste (tableau) donne les résultats :
3 5 6et
sept 9 quinze 14 22 Onze 19 17 24L'entassement de l'ensemble restant donnerait :
sept 9 Onze 14 22 quinze 19 17 24Extraire 7 et l'ajouter à la nouvelle liste donne les résultats :
3 5 6 septet
9 Onze 14 22 quinze 19 17 24L'entassement de l'ensemble restant donne :
9 Onze 14 22 quinze 19 17 24Extraire 9 et ajouter à la nouvelle liste, donne les résultats :
3 5 6 sept 9et
Onze 14 22 quinze 19 17 24L'entassement de l'ensemble restant donne :
Onze 14 17 quinze 19 22 24Extraire 11 et l'ajouter à la nouvelle liste donne les résultats :
3 5 6 sept 9 Onzeet
14 17 quinze 19 22 24L'entassement de l'ensemble restant donnerait :
14 17 quinze 19 22 24Extraire 14 et l'ajouter à la nouvelle liste donne les résultats :
3 5 6 sept 9 Onze 14et
17 quinze 19 22 24L'entassement de l'ensemble restant donnerait :
quinze 17 19 22 24Extraire 15 et l'ajouter à la nouvelle liste donne les résultats :
3 5 6 sept 9 Onze 14 quinzeet
17 19 22 24L'entassement de l'ensemble restant donnerait :
17 19 22 24Extraire 17 et l'ajouter à la nouvelle liste donne les résultats :
3 5 6 sept 9 Onze 14 quinze 17et
19 22 24L'entassement de l'ensemble restant donnerait :
19 22 24Extraire 19 et l'ajouter à la nouvelle liste donne les résultats :
3 5 6 sept 9 Onze 14 quinze 17 19et
22 24L'entassement de l'ensemble restant donne :
22 24Extraire 22 et l'ajouter à la nouvelle liste donne les résultats :
3 5 6 sept 9 Onze 14 quinze 17 19 22et
24L'entassement de l'ensemble restant donne :
24Extraire 24 et l'ajouter à la nouvelle liste donne les résultats :
3 5 6 sept 9 Onze 14 quinze 17 19 22 24et
- - -Le tableau de tas est maintenant vide. Tous les éléments qu'il avait au début sont maintenant dans le nouveau tableau (liste) et triés.
Algorithme de tri en tas
Bien que le lecteur ait pu lire dans les manuels que le tri en tas se compose de deux étapes, le tri en tas peut toujours être considéré comme composé d'une étape, qui rétrécit de manière itérative le tableau donné. Avec cela, l'algorithme pour trier avec heapsort est le suivant :
- Heapify la liste non triée.
- Extrayez le premier élément du tas et placez-le comme premier élément de la nouvelle liste.
- Heapify la liste restante.
- Extrayez le premier élément du nouveau tas et placez-le comme élément suivant de la nouvelle liste.
- Répétez les étapes précédentes dans l'ordre jusqu'à ce que la liste de tas soit vide. À la fin, la nouvelle liste est triée.
Heapsort Temps Complexité Propre
L'approche en une étape est utilisée pour déterminer la complexité temporelle du tri en tas. Supposons qu'il y ait 8 éléments non triés à trier.
Le nombre maximal d'opérations possibles pour entasser le 8 éléments est 8 .La nombre maximum possible d'opérations pour entasser le reste sept éléments est sept .
La nombre maximum possible d'opérations pour entasser le reste 6 éléments est 6 .
La nombre maximum possible d'opérations pour entasser le reste 5 éléments est 5 .
La nombre maximum possible d'opérations pour entasser le reste 4 éléments est 4 .
La nombre maximum possible d'opérations pour entasser le reste 3 éléments est 3 .
La nombre maximum possible d'opérations pour entasser le reste deux éléments est deux .
La nombre maximum possible d'opérations pour entasser le reste 1 l'élément est 1 .
Le nombre maximal d'opérations possible est de :
8 + sept + 6 + 5 + 4 + 3 + deux + 1 = 36La moyenne de ces nombres d'opérations est :
36 / 8 = 4.5Notez que les quatre derniers tas de l'illustration précédente n'ont pas changé lorsque le premier élément a été supprimé. Certains des tas précédents n'ont pas non plus changé lorsque le premier élément a été supprimé. Avec cela, un meilleur nombre moyen d'opérations principales (échanges) est de 3 et non de 4,5. Ainsi, un meilleur nombre moyen total d'opérations principales est :
24 = 8 X 3=> 24 = 8 X Journal < sous > deux < / sous > 8
depuis le journal deux 8 = 3.
En général, la complexité moyenne du temps de cas pour le tri en tas est :
O ( n.m. log2n )Où le point signifie multiplication et n est N, le nombre total d'éléments dans la liste (l'une ou l'autre liste).
Notez que l'opération d'extraction du premier élément a été ignorée. En ce qui concerne la complexité temporelle, les opérations qui prennent des temps relativement courts sont ignorées.
Coder en C++
Dans la bibliothèque d'algorithmes de C++, il existe une fonction make_heap(). La syntaxe est :
modèle < classer RandomAccessIterator, classer Comparer >constexpr annuler make_heap ( RandomAccessIterator en premier, RandomAccessIterator en dernier, Compare comp ) ;
Il prend l'itérateur pointant vers le premier élément d'un vecteur comme premier argument, puis l'itérateur pointant juste au-delà de la fin du vecteur comme dernier argument. Pour la liste non triée précédente, la syntaxe serait utilisée comme suit pour obtenir un tas minimum :
vecteur < entier > vtr = { 9 , 19 , 24 , 5 , 3 , Onze , 14 , 22 , sept , 6 , 17 , quinze } ;vecteur < entier > :: itérateur iterB = vtr. commencer ( ) ;
vecteur < entier > :: itérateur iterE = vtr. fin ( ) ;
make_heap ( iterB, iterE, supérieur < entier > ( ) ) ;
Ce code transforme un contenu vectoriel en une configuration de tas minimum. Dans les vecteurs C++ suivants, deux vecteurs seront utilisés au lieu de deux tableaux.
Pour copier et renvoyer le premier élément d'un vecteur, utilisez la syntaxe vectorielle :
constexpr avant de référence ( ) ;Pour supprimer le premier élément d'un vecteur et le jeter, utilisez la syntaxe vectorielle :
constexpr effacement de l'itérateur ( position const_iterator )Pour ajouter un élément à la fin d'un vecteur (élément suivant), utilisez la syntaxe vectorielle :
constexpr annuler repousser ( constante J & X ) ;Le début du programme est :
#include#include
#include
utilisant espace de noms std ;
Les bibliothèques d'algorithmes et de vecteurs sont incluses. Ensuite dans le programme se trouve la fonction heapsort(), qui est :
annuler tri en tas ( vecteur < entier > & ancienV, vecteur < entier > & nouveauV ) {si ( ancienV. Taille ( ) > 0 ) {
vecteur < entier > :: itérateur iterB = ancienV. commencer ( ) ;
vecteur < entier > :: itérateur iterE = ancienV. fin ( ) ;
make_heap ( iterB, iterE, supérieur < entier > ( ) ) ;
entier Suivant = ancienV. de face ( ) ;
ancienV. effacer ( iterB ) ;
nouveauV. repousser ( Suivant ) ;
tri en tas ( ancienV, nouveauV ) ;
}
}
C'est une fonction récursive. Il utilise la fonction make_heap() de la bibliothèque d'algorithmes C++. Le deuxième segment de code dans la définition de la fonction extrait le premier élément de l'ancien vecteur après la construction du tas et l'ajoute comme élément suivant pour le nouveau vecteur. Notez que dans la définition de la fonction, les paramètres du vecteur sont des références, tandis que la fonction est appelée avec les identifiants (noms).
Une fonction principale C++ appropriée pour cela est :
entier principale ( entier argc, carboniser ** argv ){
vecteur < entier > ancienV = { 9 , 19 , 24 , 5 , 3 , Onze , 14 , 22 , sept , 6 , 17 , quinze } ;
vecteur < entier > nouveauV ;
tri en tas ( ancienV, nouveauV ) ;
pour ( entier je = 0 ; je < nouveauV. Taille ( ) ; je ++ ) {
écoute << nouveauV [ je ] << ' ' ;
}
écoute << fin ;
revenir 0 ;
}
La sortie est :
3 5 6 sept 9 Onze 14 quinze 17 19 22 24trié (complètement).
Conclusion
L'article a discuté en détail de la nature et de la fonction de Heap Sort, communément appelé Heapsort, en tant qu'algorithme de tri. Heapify Time Complexity, Heapsort illustration et Heapsort en tant qu'algorithme ont été couverts et soutenus par des exemples. La complexité temporelle moyenne pour un programme de tri en tas bien écrit est O(nlog(n))