1. Je dois parler des arbres binaires
Pour comprendre le tas, vous devez d'abord comprendre l'arbre binaire. En informatique, un arbre binaire est une structure d'arbre avec au plus deux sous-sous-sous-nœuds. Habituellement, les sous-arbres sont appelés "sous-arbre gauche" et "sous-arbre droit". Les arbres binaires sont souvent utilisés pour implémenter des arbres de recherche binaires et des tas binaires.
Chaque nœud d'un arbre binaire a au plus deux sous-sous (nœuds avec des degrés supérieurs à 2). Les sous-arbres d'un arbre binaire peuvent être divisés en gauche et en droite, et l'ordre ne peut pas être inversé. La i-thoryer de l'arbre binaire a au plus 2i - 1 nœud; L'arbre binaire avec une profondeur de K a au plus 2k - 1 nœud; Pour tout arbre binaire T, si le nombre de nœuds terminaux est n0 et le nombre de nœuds avec un degré de 2 est n2, n0 = n2 + 1.
Il existe trois principales différences entre un arbre et un arbre binaire:
Le nombre de nœuds dans l'arbre est d'au moins 1, tandis que le nombre de nœuds dans l'arbre binaire peut être 0.
Il n'y a pas de limite au degré maximal de nœuds dans l'arbre, tandis que le degré maximal de nœuds dans l'arbre binaire est 2
Il n'y a pas de différence entre la gauche et la droite dans les nœuds d'un arbre, alors qu'il n'y a pas de différence entre la gauche et la droite dans les nœuds d'un arbre binaire.
Les arbres binaires sont divisés en arbres binaires complets et arbres binaires pleins.
Arbre binaire complet: un arbre avec une profondeur de k et a un nœud 2k - 1 est appelé un arbre binaire complet
(arbre binaire complet avec profondeur 3)
Arbre binaire complet: un arbre binaire avec n nœuds avec profondeur k. Il est appelé un arbre binaire complet si et seulement si chacun de ses nœuds correspond à un nœud avec des numéros de séquence de 1 à n dans un arbre binaire complet avec la profondeur k.
(Arbre binaire complet avec profondeur 3)
2. Qu'est-ce qu'un tas?
Un tas (tas binaire) peut être considéré comme un arbre binaire complet. Une "excellente" propriété d'un arbre binaire complet est que, à l'exception de la couche inférieure, chaque couche est pleine, ce qui permet à le tas d'être représenté par un tableau (les arbres binaires généraux ordinaires sont généralement représentés par des listes liées comme conteneurs de base), et chaque nœud correspond à un élément dans le tableau.
La figure suivante montre la relation entre un tas et un tableau
(La relation entre le tas et le tableau)
Pour l'indice donné I d'un nœud, il peut être facilement calculé pour l'indice du nœud parent et du nœud enfant de ce nœud:
Parent (i) = plancher (i / 2), l'indice de nœud parent de i
Gauche (i) = 2i, l'indice de nœud enfant gauche de i
Droit (i) = 2i + 1, l'indice de nœud enfant droit de i
Il existe généralement deux types de tas binaires: le plus grand tas et le plus petit tas.
Tas maximum:
La valeur d'élément maximale dans le tas maximum apparaît au nœud racine (haut du tas)
La valeur de l'élément de chaque nœud parent dans le tas est supérieure ou égale à son nœud enfant (s'il existe)
(Tas maximum)
Tas minimum:
La valeur minimale de l'élément dans le tas minimum apparaît au nœud racine (haut du tas)
La valeur de l'élément de chaque nœud parent dans le tas est inférieure ou égale à son nœud enfant (s'il existe)
(Pile minimum)
3. Principe du tri des tas
Le tri du tas est de supprimer le nombre maximum en haut du tas maximum, de continuer à ajuster le tas restant au tas maximum et à éliminer le nombre maximum en haut du tas. Ce processus se poursuit jusqu'à ce qu'il n'y ait qu'un seul numéro restant. Définissez les opérations suivantes dans le tas:
Max-HEAPIFY: Ajustez le nœud d'extrémité du tas pour que le nœud enfant soit toujours plus petit que le nœud parent
Créez un tas maximum (build-max-heap): réorganisez toutes les données du tas pour en faire le tas maximum
Tas-sort: supprimez le nœud racine des premières données et effectuez un fonctionnement récursif du réglage du tas maximum
Avant de poursuivre la discussion suivante, un problème qui doit être noté est: les tableaux sont tous basés sur zéro, ce qui signifie que notre modèle de structure de données de tas changera.
(Basé sur zéro)
De même, plusieurs formules de calcul doivent également être ajustées en conséquence:
Parent (i) = plancher ((i-1) / 2), l'indice de nœud parent de i
Gauche (i) = 2i + 1, l'indice de nœud enfant gauche de i
Droit (i) = 2 (i + 1), l'indice de nœud enfant droit de i
La fonction du réglage du tas max (maxheapify) est de maintenir les propriétés du plus grand tas et est le sous-programme central pour créer le plus grand tas. Le processus de fonctionnement est illustré sur la figure:
(Max-Heapify)
Étant donné que le tas viole toujours la nature du tas après un ajustement, des tests récursifs sont nécessaires afin que l'ensemble du tas satisfait la nature du tas. Il peut être exprimé en JavaScript comme suit:
/ ** * Vérifier à partir de l'index et maintenir les propriétés de tas maximales * * @Array * * L'index de démarrage de la vérification @index * * @HapSize Heap Size * ** / Fonction MaxHeapify (Array, Index, HeapSize) {var imax = index, ileft = 2 * index + 1, iright = 2 * (index + 1); if (ileft <heapSize && array [index] <array [ileft]) {iMax = ileft; } if (Iright <heapSize && array [iMax] <array [iright]) {iMax = iright; } if (iMax! = index) {swap (array, iMax, index); MaxHeapify (tableau, IMAX, HEAPSIZE); // Recursive Ajustement}} Fonction Swap (Array, I, J) {var temp = Array [i]; array [i] = array [j]; Array [j] = temp;}D'une manière générale, la récursivité est principalement utilisée dans la méthode de division et de traitement, et il n'y a pas besoin de division et de traitement ici. De plus, les appels récursifs nécessitent une pression / compensation de pile, ce qui présente un léger inconvénient des performances par rapport à l'itération. Bien sûr, cela peut être ignoré selon la règle du 20/80. Mais si vous pensez que l'utilisation de la récursivité vous mettra mal à l'aise, vous pouvez également utiliser l'itération, comme ce qui suit:
/ ** * Vérifiez à partir de l'index et maintenez les propriétés de tas maximales * * @Array * * L'indice de démarrage du chèque @index * * @HapSize Tas Size * ** / fonction maxHeapify (tableau, index, heapSize) {var imax, ileft, iright; while (true) {iMax = index; ileft = 2 * index + 1; IRIGHT = 2 * (Index + 1); if (ileft <heapSize && array [index] <array [ileft]) {iMax = ileft; } if (Iright <heapSize && array [iMax] <array [iright]) {iMax = iright; } if (iMax! = index) {swap (array, iMax, index); index = iMax; } else {break; }}} fonction swap (array, i, j) {var temp = array [i]; array [i] = array [j]; Array [j] = temp;}Le but de créer un tas maximum (build-max-heap) est de transformer un tableau en un tas maximum, acceptant deux paramètres de la taille du tableau et du tas. Build-Max-Heap appellera Max-Hapify de bas en haut pour transformer le tableau et construire le tas maximum. Étant donné que Max-Heapify peut garantir que les nœuds après l'indice, je respecte les propriétés du plus grand tas, l'appel ascendant vers Max-Heapify peut maintenir cette propriété pendant le processus de transformation. Si l'élément de numéro de tas maximum est n, alors build-max-heap appelle max-hapify en séquence à partir du parent (n). Le processus est le suivant:
La description est la suivante dans JavaScript:
fonction buildMaxHeap (array, heapSize) {var i, iparent = math.floor ((heapSize - 1) / 2); pour (i = iparent; i> = 0; i--) {maxHeapify (array, i, heapSize); }}Heap-Sort est l'algorithme d'interface pour le tri des tas. Le tas-sort appelle d'abord Build-Max-Heap pour transformer le tableau en tas maximum, puis échange les éléments supérieurs et inférieurs du tas, puis monte le fond et appelle enfin Max-Heapify pour maintenir les propriétés maximales du tas. Étant donné que l'élément supérieur du tas doit être l'élément le plus grand du tas, après une opération, le plus grand élément présent dans le tas est séparé du tas du tas, et après des heures N-1 répétées, le réseau est disposé. L'ensemble du processus est le suivant:
La description est la suivante dans JavaScript:
fonction heapsort (array, heapSize) {buildMaxHeap (array, heapSize); for (int i = heapSize - 1; i> 0; i--) {swap (array, 0, i); MaxHeaPify (Array, 0, I); }}4. Implémentation de la langue JavaScript
Enfin, organisez ce qui précède en code JavaScript complet comme suit:
fonction heapsort (array) {fonction swap (array, i, j) {var temp = array [i]; array [i] = array [j]; Array [j] = temp; } fonction maxheapify (array, index, heapSize) {var iMax, ileft, iright; while (true) {iMax = index; ileft = 2 * index + 1; IRIGHT = 2 * (Index + 1); if (ileft <heapSize && array [index] <array [ileft]) {iMax = ileft; } if (Iright <heapSize && array [iMax] <array [iright]) {iMax = iright; } if (iMax! = index) {swap (array, iMax, index); index = iMax; } else {break; }}} fonction buildMaxHeap (array) {var i, iparent = math.floor (array.length / 2) - 1; pour (i = iparent; i> = 0; i--) {maxHeapify (array, i, array.length); }} fonction tri (array) {buildMaxHeap (array); pour (var i = array.length - 1; i> 0; i--) {swap (array, 0, i); MaxHeaPify (Array, 0, I); } Return Array; } return tri (tableau);}5. Application de l'algorithme de tri de tas
(1) Performance / complexité de l'algorithme
La complexité temporelle du tri des tas est très stable (nous pouvons voir qu'il n'est pas sensible aux données d'entrée) et est une complexité O (nn), le meilleur cas est le même que le pire des cas.
Cependant, sa complexité spatiale varie selon la mise en œuvre. Ce qui précède traite de deux complexités communes: O (n) et O (1). Sur la base du principe de la sauvegarde de l'espace, je recommande la méthode de complexité O (1).
(2) Stabilité de l'algorithme
Il existe un grand nombre de processus de filtrage et de déplacement dans le tri des tas, qui appartient à un algorithme de tri instable.
(3) Scénario applicable de l'algorithme
Le tri du tas entraînera des frais généraux relativement importants dans le processus de construction du tas et de réglage du tas, et il n'est pas applicable lorsqu'il y a peu d'éléments. Cependant, lorsqu'il y a de nombreux éléments, c'est toujours un bon choix. Surtout lors de la résolution de problèmes tels que "le nombre de n top n grand", c'est presque l'algorithme préféré.