Aperçu
Le tri du tas est un tri de sélection d'arbres, qui est une amélioration efficace du tri de sélection directe.
Le tas est défini comme suit: une séquence de n éléments (k1, k2, ..., kN), si et seulement si satisfait:
Cela s'appelle une pile à ce moment-là. Comme le montre la définition du tas, l'élément supérieur du tas (c'est-à-dire le premier élément) doit être le plus petit élément (petit tas supérieur) ou le plus grand élément (grand tas supérieur).
Si un tas est stocké dans un réseau unidimensionnel, le tas correspond à un arbre complètement binaire, et les valeurs de tous les nœuds non feuilles (nœuds avec enfants) ne sont pas plus que (ou pas moins que) les valeurs de leurs enfants, et les valeurs du nœud racine (élément supérieur du tas) sont les plus petites (ou les plus importantes).
(a) Grande séquence de tas supérieurs: (96, 83, 27, 38, 11, 09)
(b) Small top tas séquence: (12, 36, 24, 85, 47, 30, 53, 91)
Initialement, la séquence de n nombres à tri est considérée comme un arbre binaire stocké séquentiellement (arborescence binaire de stockage unidimensionnelle), ajustez leur ordre de stockage pour en faire un tas, émettez l'élément supérieur du tas pour obtenir l'élément le plus petit (ou le plus grand) des éléments N. Redirettez ensuite les éléments N-1 restants pour devenir un tas, sortez l'élément supérieur du tas et obtenez l'élément qui est le deuxième petit (ou le deuxième grand) parmi les n éléments. Et ainsi de suite jusqu'à ce que vous obteniez enfin une séquence commandée avec n nœuds. Appelez ce tri du processus.
Étapes et exemples
Il y a deux problèmes à résoudre dans la mise en œuvre du tri des tas:
(1) comment construire n nombres à tri en piles;
(2) Après avoir sorti l'élément supérieur du tas, comment ajuster les éléments N-1 restants pour en faire un nouveau tas.
Construire la méthode du tas (petit tas de tas):
Le processus de construction d'un tas pour la séquence initiale est un processus de dépistage répété.
Un arbre binaire complet de n nœuds, puis le dernier nœud est le sous-arbre du nœud n / 2ème.
Le filtre commence par le sous-arbre avec le nœud n / 2ème comme la racine (N / 2 est le dernier nœud avec le sous-arbre), de sorte que le sous-arbre devient un tas.
Ensuite, filtrez les sous-arbres avec chaque nœud sous forme de racine dans la séquence vers l'avant pour en faire un tas jusqu'à ce que le nœud racine.
Comme le montre la figure, la séquence désordonnée du processus initial de construction d'un tas: (49, 38, 65, 97, 76, 13, 27, 49)
(a) Séquence non ordonnée, arbre binaire initial, 97 (8/2 = nœud 4) est le nœud parent du dernier nœud (49).
(b) 97> = 49, remplacer la position, puis filtrer le nœud précédent 65 de N / 2.
(c) 13 <= 27 et 65> = 13, remplacer les positions de 65 et 13, puis remplacer 38 (les deux supérieurs à celui-ci, aucune opération n'est requise), filtre 49.
(d) 13 <= 38 et 49> = 13, remplacez les positions de 49 et 13, 49> = 27, remplacez les positions de 49 et 27.
(e) Obtenez enfin un tas, 13 est le nombre minimum que nous obtenons.
Méthodes pour ajuster le tas (petit tas supérieur):
Un tas d'éléments M est fourni. Après avoir sorti les éléments supérieurs du tas, des éléments M-1 sont laissés. L'élément inférieur du tas est alimenté en haut du tas, et le tas est détruit, car le nœud racine ne répond pas aux propriétés du tas.
Échangez le nœud racine avec des éléments plus petits dans les sous-arbres gauche et droit.
Si vous êtes échangé avec le sous-arbre gauche: Si le tas de sous-arbre gauche est corrompu, répétez la méthode (2).
Si vous êtes échangé avec le sous-arbre droit, répétez la méthode (2) si le tas de sous-arbre droit est détruit.
Continuez à effectuer l'opération d'échange ci-dessus sur des sous-arbres qui ne répondent pas aux propriétés du tas jusqu'à ce que les nœuds de feuille et le tas soient construits.
Pour ajuster le tas, il vous suffit de considérer les nœuds corrompus et d'autres nœuds n'ont pas besoin d'être ajustés.
Implémentation du code (Java)
Exécutez le code et comparez les commentaires avec l'exemple ci-dessus des étapes de comparaison.
package com.coder4j.main; classe publique Heapsort {/ ** * s'adapter à un petit tas supérieur (le résultat est de grand à petit après le tri) * * @param le tableau est le tableau de tas à ajuster * @param s est la position de l'élément de tableau à ajuster * @param le long est la longueur du tableau * * / public static vide heapadjust (int [int [int S, in int.) tmp = array [s]; int child = 2 * s + 1; // La position du nœud enfant gauche System.out.println ("Le nœud à ajuster est: array [" + s + "] =" + tmp); tandis que (enfant <longueur) {// enfant + 1 est le bon enfant ajustant actuellement le nœud // s'il y a un enfant droit et est plus petit que l'enfant gauche, utilisez l'enfant droit pour comparer avec le nœud, sinon utilisez l'enfant gauche si (enfant + 1 <longueur && array [enfant]> array [enfant + 1]) {enfant ++; } System.out.println ("sera avec le Array Child [" + Child + "] =" + Array [Child] + "Compare"); // Si le plus petit enfant est plus petit que ce nœud if (array [s]> array [enfant]) {System.out.println ("l'enfant est plus petit que lui, swap position"); array [s] = array [enfant]; // déplacer le plus petit enfant vers le haut et remplacer le nœud actuel pour être ajusté s = enfant; // déplacez le nœud ajusté à la position d'origine du tableau d'enfant plus jeune [enfant] = TMP; Enfant = 2 * S + 1; // Continuez à juger si le nœud doit être ajusté doit continuer à être ajusté si (enfant> = longueur) {System.out.println ("Il n'y a pas d'enfants, l'ajustement est terminé"); } else {System.out.println ("Continuez à se comparer avec le nouvel enfant"); } // continuer; } else {System.out.println ("Les enfants sont plus âgés qu'eux, l'ajustement est terminé"); Break; // Le nœud actuel à régler est plus petit que ses enfants gauche et droit, et il n'a pas besoin d'être ajusté, quittez directement}}} / ** * Ajuster à un grand tas supérieur (le résultat est de petit à grand après le tri) * * @param Array est le tableau de tas à ajuster * @Param S est la position de l'élément de l'arrêt à ajuster * @Param Longue heapAdJustB (int [] array, int s, int longueur) {int tmp = array [s]; int child = 2 * s + 1; // La position du nœud enfant gauche System.out.println ("Le nœud à ajuster est: array [" + s + "] =" + tmp); tandis que (enfant <longueur) {// enfant + 1 est le bon enfant ajustant actuellement le nœud // s'il y a un enfant droit et qu'il est plus grand que l'enfant gauche, utilisez le bon enfant pour comparer avec le nœud, sinon utilisez l'enfant gauche si (enfant + 1 <longueur && array [enfant] <array [enfant + 1]) {enfant ++; } System.out.println ("sera avec le Array Child [" + Child + "] =" + Array [Child] + "Compare"); // Si l'enfant plus âgé est plus grand que ce nœud if (array [s] <array [enfant]) {System.out.println ("L'enfant est plus grand que lui, la position d'échange"); array [s] = array [enfant]; // déplacer l'enfant plus âgé vers le haut et remplacer le nœud actuel à ajuster s = enfant; // déplacez le nœud ajusté à la position d'origine du tableau d'enfant plus âgé [enfant] = TMP; Enfant = 2 * S + 1; // Continuez à juger si le nœud doit être ajusté doit être ajusté si (enfant> = longueur) {System.out.println ("Il n'y a pas d'enfants, l'ajustement est terminé"); } else {System.out.println ("Continuez à se comparer avec le nouvel enfant"); } // continuer; } else {System.out.println ("Les enfants sont plus petits qu'eux, l'ajustement est terminé"); Break; // Le nœud actuel à ajuster est plus grand que ses enfants gauche et droite, et quitter directement sans ajustement}}} / ** * Algorithme de tri du tas * * @param Array * @param inverse True in Reverse Ordre, False in Positive Ordre * / Public Static Void Heapsort (Int [] Table / 2, afin d'ajuster chaque nœud vers le haut pour se conformer au tas System.out.println ("Démarrage du tas initial"); for (int i = (array.length - 1) / 2; i> = 0; i--) {if (inverse) {heapAdJusts (array, i, array.length); } else {heapAdJustB (array, i, array.length); }} System.out.println ("Initial Heap End"); for (int i = array.length - 1; i> 0; i--) {// échange l'élément de haut du tas h [0] et le dernier élément du tas int tmp = array [i]; array [i] = array [0]; Array [0] = TMP; // Après chaque échange de l'élément supérieur du tas et du dernier élément du tas, le tas doit être ajusté si (inverse) {tasajuste (tableau, 0, i); } else {HeapAdJustB (array, 0, i); }}} public static void main (String [] args) {int [] array = {49, 38, 65, 97, 76, 13, 27, 49}; heapsort (array, false); pour (int i: array) {System.out.print (i + ""); }}}Résultats en cours:
Le nœud à ajuster au début du tas initial est: le tableau [3] = 97 L'enfant sera plus petit avec le tableau d'enfant [7] = 49 L'enfant est plus petit avec l'enfant, et le nœud à ajuster à la fin du réglage est: le tableau [2] = 65 = 38 L'enfant est plus grand avec le tableau d'enfants [3] = 49 L'enfant est plus grand avec le tableau d'enfants [0] = 49 L'enfant est plus petit avec le tableau d'enfant [2] = 13 L'enfant est plus petit avec le tableau d'enfant [6] = 27 L'enfant est plus petit que la position d'échange, et il n'y a pas d'enfant dans la position d'échange. Le nœud à ajuster après le réglage est: tableau [0] = 97 L'enfant est plus petit que l'enfant. L'enfant est plus petit que l'enfant. La position d'échange continue de se comparer avec le nouvel enfant. L'enfant est un tableau [6] = 49 L'enfant est plus petit que la position d'échange, et il n'y a pas d'enfant en position d'échange. Le nœud à ajuster après le réglage est: tableau [0] = 97 L'enfant est plus petit que l'enfant. L'enfant est plus petit que l'enfant. L'enfant est plus petit que l'enfant. L'enfant est un tableau [1] = 38 L'enfant est plus petit que l'enfant. L'enfant est un tableau [3] = 49 L'enfant est plus petit que l'enfant. L'enfant est plus petit que la position d'échange. Le nœud à ajuster après l'ajustement est: tableau [0] = 65 L'enfant est un tableau [1] = 49 L'enfant est plus petit que l'enfant, et la position d'échange continue d'être comparée au nouvel enfant. L'enfant sera plus grand que l'enfant. Le nœud à ajuster après le réglage est: tableau [0] = 76 L'enfant est plus grand que l'enfant. Le nœud à régler après le réglage est: tableau [0] = 76 L'enfant est plus petit que l'enfant. Le nœud à ajuster après le réglage est: tableau [0] = 49 L'enfant est plus petit que l'enfant. Le nœud à ajuster après le réglage est: tableau [0] = 97 L'enfant est plus petit que l'enfant. Le nœud à régler après le réglage est: Array [0] = 97 76 65 49 49 38 27 13
PS: la différence entre le tri du tas et le tri direct d'insertion
Dans l'ordre de sélection directe, afin de sélectionner l'enregistrement avec le plus petit mot-clé de R [1..N], la comparaison N-1 doit être effectuée, puis sélectionner l'enregistrement avec le plus petit mot-clé en R [2..N], les comparaisons N-2 doivent être effectuées. En fait, dans les comparaisons N-2 suivantes, de nombreuses comparaisons peuvent avoir été faites dans les comparaisons N-1 précédentes, mais comme ces résultats de comparaison n'ont pas été conservés dans l'ordre précédent, ces opérations de comparaison ont été répétées au cours de l'ordre suivant.
Le tri de tas peut économiser une partie des résultats de comparaison grâce à une structure d'arbre, ce qui peut réduire le nombre de comparaisons.