Explication graphique détaillée de l'algorithme de tri de tas Heap Sort et de l'implémentation du code JavaScript_Connaissances de base

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 arborescente dans laquelle chaque nœud possède au plus deux sous-arbres. 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 possède au plus deux sous-arbres (il n'y a pas de nœud de degré supérieur à 2). Les sous-arbres d'un arbre binaire sont divisés en sous-arbres gauche et droit, et l'ordre ne peut pas être inversé. Le i-ème niveau d'un arbre binaire a au plus 2i - 1 nœuds ; un arbre binaire de profondeur k a au plus 2k - 1 nœuds pour tout arbre binaire T, si le nombre de nœuds terminaux est n0, le nombre de nœuds ; de degré 2 est n2, alors n0 = n2 + 1.
Trois différences principales entre les arbres et les arbres binaires :
Le nombre de nœuds d'un arbre doit être au moins 1, tandis que le nombre de nœuds d'un arbre binaire peut être 0
Il n'y a pas de limite au degré maximum d'un nœud dans un arbre, alors que le degré maximum d'un nœud dans un arbre binaire est 2
Les nœuds de l'arbre ne sont pas divisés en gauche et droite, tandis que les nœuds de l'arbre binaire sont divisés en gauche et droite
Les arbres binaires sont divisés en arbres binaires complets et arbres binaires complets
Arbre binaire complet : Un arbre de profondeur k et 2k - 1 nœuds est appelé un arbre binaire complet

(arbre binaire complet avec profondeur 3)
Arbre binaire complet : Un arbre binaire de profondeur k et n nœuds Si et seulement si chacun de ses nœuds correspond aux nœuds numérotés de 1 à n dans l'arbre binaire complet de profondeur k, on l'appelle un arbre binaire complet
.

(arbre binaire complet de 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 chaque niveau, à l'exception du niveau le plus bas, est plein, ce qui permet au tas d'utiliser des tableaux pour être représenté (ordinaire). les arbres binaires sont généralement représentés par des listes chaînées comme conteneurs de base), chaque nœud correspond à un élément du tableau.
Comme indiqué ci-dessous, c'est la relation entre un tas et un tableau

(Interrelation entre le tas et le tableau)
Pour un indice i donné d'un nœud, les indices du nœud parent et du nœud enfant de ce nœud peuvent être facilement calculés :
Parent(i) = floor(i/2), l'indice du nœud parent de i
Gauche(i) = 2i, i est l'indice gauche
Right(i) = 2i + 1, i est l'indice du nœud enfant de droite

Les tas binaires sont généralement divisés en deux types : le tas maximum et le tas minimum.
Tas maximum :
La valeur maximale de l'élément dans le tas max apparaît au nœud racine (en 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 plus petite valeur d'élément dans le tas min apparaît au nœud racine (en 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)

(min tas)
3. Principe du tri en tas
Le tri par tas consiste à retirer le nombre maximum en haut du tas maximum, à continuer d'ajuster le tas restant au tas maximum et à retirer à nouveau le nombre maximum en haut du tas. Ce processus se poursuit jusqu'à là. n'est qu'un nombre restant. Définissez les opérations suivantes sur le tas :
Max-Heapify : Ajustez les nœuds enfants finaux du tas afin que les nœuds enfants soient toujours plus petits que le nœud parent
Créer un tas maximum (Build-Max-Heap) : réorganisez toutes les données du tas pour en faire un tas maximum
Heap-Sort : supprimez le nœud racine des premières données et effectuez une opération récursive d'ajustement maximal du tas
Avant de poursuivre la discussion suivante, une chose à noter est que les tableaux sont tous de base zéro, ce qui signifie que notre modèle de structure de données de tas va changer

(Basé zéro)
En conséquence, plusieurs formules de calcul doivent également être ajustées en conséquence :
Parent(i) = floor((i-1)/2), l'indice du nœud parent de i
Left(i) = 2i + 1, l'indice du nœud enfant gauche de i
Right(i) = 2(i + 1), i est l'indice du nœud enfant de droite
La fonction d'ajustement du tas maximum (MAX-HEAPIFY) est de maintenir les propriétés du tas maximum et constitue le sous-programme principal pour créer le tas maximum. Le processus fonctionnel est comme indiqué dans la figure :
.

(Max-Heapify)
Étant donné qu'après un ajustement, le tas viole toujours les propriétés du tas, des tests récursifs sont nécessaires pour que l'ensemble du tas satisfasse les propriétés du tas. Cela peut être exprimé en JavaScript comme suit :

.

/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @heapSize 堆大小
 *
 **/
function 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(array, iMax, heapSize); // 递归调整
 }
}

function swap(array, i, j) {
 var temp = array[i];
 array[i] = array[j];
 array[j] = temp;
}

De manière générale, la récursivité est principalement utilisée dans la méthode diviser pour régner, mais diviser pour régner n'est pas obligatoire ici. De plus, les appels récursifs nécessitent de pousser/effacer la pile, ce qui présente un léger inconvénient en termes de performances par rapport à l'itération. Bien entendu, en suivant la règle des 20/80, cela peut être ignoré. Mais si vous pensez que l'utilisation de la récursivité vous mettra mal à l'aise, vous pouvez également utiliser l'itération, comme celle-ci :

/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @heapSize 堆大小
 *
 **/
function 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;
  }
 }
}

function swap(array, i, j) {
 var temp = array[i];
 array[i] = array[j];
 array[j] = temp;
}

La fonction de création d'un tas maximum (Build-Max-Heap) est de transformer un tableau en un tas maximum. Il accepte deux paramètres : le tableau et la taille du tas appelleront Max-Heapify de bas en haut. top Transformez le tableau et créez un tas maximum. Étant donné que Max-Heapify peut garantir que les nœuds après le nœud avec l'indice i satisfont à la propriété de tas maximum, l'appel ascendant de Max-Heapify peut conserver cette propriété pendant le processus de transformation. Si le nombre d'éléments dans le tas maximum est n, alors Build-Max-Heap commence à partir de Parent(n) et appelle Max-Heapify dans l'ordre. Le processus est le suivant :

Décrit en JavaScript comme suit :

function buildMaxHeap(array, heapSize) {
 var i,
   iParent = Math.floor((heapSize - 1) / 2);
   
 for (i = iParent; i >= 0; i--) {
  maxHeapify(array, i, heapSize);
 }
}

Heap-Sort est l'algorithme d'interface du tri par tas. Heap-Sort appelle d'abord Build-Max-Heap pour transformer le tableau en un tas maximum, puis échange les éléments supérieur et inférieur du tas, puis élève le bas, et enfin, rappelez Max-Heapify pour conserver les propriétés maximales du tas. Étant donné que l'élément supérieur du tas doit être le plus grand élément du tas, après une opération, le plus grand élément existant dans le tas est séparé du tas. Après avoir répété n-1 fois, le tableau est organisé. L'ensemble du processus est le suivant :

Décrit en JavaScript comme suit :

function 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 du langage JavaScript
Enfin, organisez ce qui précède dans le code javascript complet comme suit :

function heapSort(array) {

 function swap(array, i, j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
 }

 function 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;
   }
  }
 }

 function buildMaxHeap(array) {
  var i,
   iParent = Math.floor(array.length / 2) - 1;

  for (i = iParent; i >= 0; i--) {
   maxHeapify(array, i, array.length);
  }
 }

 function sort(array) {
  buildMaxHeap(array);

  for (var i = array.length - 1; i > 0; i--) {
   swap(array, 0, i);
   maxHeapify(array, 0, i);
  }
  return array;
 }

 return sort(array);
}

5. Application de l'algorithme de tri par tas

(1) Performance/complexité de l'algorithme
La complexité temporelle du tri par tas est très stable (on peut voir qu'elle n'est pas sensible aux données d'entrée), c'est une complexité O(n㏒n), et le meilleur des cas est le même que le pire des cas.
Cependant, sa complexité spatiale varie d’une mise en œuvre à l’autre. Deux complexités courantes ont été discutées ci-dessus : O(n) et O(1). Conformément au principe d'économie d'espace, je recommande la méthode de complexité O(1).

(2) Stabilité de l'algorithme
Le tri par tas implique un grand nombre de processus de filtrage et de déplacement et constitue un algorithme de tri instable.

(3) Scénarios applicables à l'algorithme
Le tri du tas entraînera une surcharge relativement importante dans le processus d'établissement et d'ajustement du tas, et ne convient pas lorsqu'il y a peu d'éléments. Cela reste cependant un bon choix lorsqu’il y a de nombreux éléments. Surtout lors de la résolution de problèmes tels que « les n premiers plus grands nombres », c’est presque l’algorithme préféré.