Cet article présente principalement l'implémentation du tri par tas dans JS, qui a une certaine valeur de référence. Maintenant, je le partage avec tout le monde. Les amis dans le besoin peuvent se référer à
Le tas est un arbre binaire complet.
Arbre binaire complet : à l'exception de la dernière couche de l'arbre binaire, le nombre de nœuds dans les autres couches atteint le maximum, et tous les nœuds de la dernière couche sont concentrés sur la gauche (lorsque les nœuds de gauche sont pleins, les nœuds ne peuvent manquer qu'à droite).
Grand tas supérieur : le nœud racine est la valeur maximale et la valeur de chaque nœud est supérieure ou égale à la valeur de son nœud enfant.
Petit tas supérieur : le nœud racine est la valeur minimale et la valeur de chaque nœud est inférieure ou égale à la valeur de son nœud enfant.
Stockage par tas : le tas est implémenté par un tableau, ce qui équivaut à un parcours par ordre de niveau d'un arbre binaire. Comme indiqué ci-dessous :
Pour le nœud i, ses nœuds enfants Les points sont 2i+1 et 2i+2.
Nous devons maintenant trier l'arbre binaire ci-dessus par ordre croissant, qui est divisé en trois étapes :
Convertissez l'arbre binaire initial en un grand tas supérieur (heapify). À ce stade, le nœud racine est la valeur maximale et il est échangé avec le dernier nœud.
À l'exception du dernier nœud, convertissez le nouveau tas composé des nœuds restants en un grand tas supérieur. À ce stade, le nœud racine est la valeur sous-maximale, et c'est le cas. échangé avec le dernier nœud.
Répétez l'étape 2 jusqu'à ce que le nombre d'éléments dans le tas soit de 1 (ou que la longueur de son tableau correspondant soit de 1) et que le tri soit terminé.
Le processus est illustré en détail ci-dessous :
Initialisez le grand tas supérieur, sélectionnez d'abord le dernier nœud non-feuille ( nous avons seulement besoin d'ajuster la relation de taille entre le nœud parent et le nœud enfant. La relation de taille entre les nœuds feuilles n'a pas besoin d'être ajustée). Supposons que le tableau soit arr, alors l'indice du premier nœud non-feuille est : i = Math.floor(arr.length/2 - 1) = 1, qui est le nombre 4, comme indiqué dans la case en pointillés de la figure , trouvez trois nombres La valeur maximale est échangée avec le nœud parent.
Ensuite, l'indice i est décrémenté de 1 (c'est-à-dire, en commençant par le premier nœud non-feuille, en parcourant tous les nœuds non-feuilles de droite à gauche, et de de bas en haut). Chaque ajustement ultérieur est le même : trouvez la valeur maximale entre les nœuds parent et enfant et effectuez un échange.
Après l'échange des nombres 6 et 1 dans cette étape, l'ordre du tas composé des nombres [1,5,4] est erroné, et une étape d'ajustement est requis. Par conséquent, il est important de noter que chaque fois que vous effectuez un ajustement sur un nœud non-feuille, vous devez observer si cela affectera l'ordre des sous-tas !
Après cet ajustement, le nœud racine a la valeur maximale, formant un grand tas supérieur, et le nœud racine est échangé avec le dernier nœud.
À l'exception du dernier nœud actuel 6 (c'est-à-dire la valeur maximale), formez un nouveau tas des nœuds restants [4,5,3,1] et convertissez-le en un grand tas supérieur (Faites attention à l'observation. À ce stade, les autres nœuds autres que le nœud racine répondent tous aux caractéristiques d'un grand tas supérieur, vous pouvez donc commencer à vous ajuster à partir du nœud racine 4, c'est-à-dire trouver la position où 4 devrait l'être).
Répétez ensuite l'étape 2 jusqu'à ce que le nombre de les éléments dans le tas sont 1 :
Le nombre d'éléments dans le tas est 1, trier Terminer.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
|
Notes du programme : organisez le tas sous le nœud i en un tas supérieur. Notez que la base de cette étape est en fait : supposer que le sous-tas sous le nœud i est déjà. Pour un grand tas supérieur, la fonction implémentée par la fonction ajusterHeap consiste en fait à trouver la position correcte du nœud i dans le tas incluant le nœud i. Lors de l'exécution du premier tas plus tard, une boucle for est écrite dans heapSort. À partir du premier nœud non-feuille, l'opération ajusterHeap est effectuée sur chaque nœud non-feuille, il est donc satisfait que dans chaque ajusterHeap, le nœud Le sous-. le tas en dessous de i est déjà un grand tas supérieur.
Analyse de complexité : la fonction ajusterHeap équivaut à parcourir un seul nœud pour chaque niveau du tas, car
la profondeur d'un arbre binaire complet avec n nœuds est [log2n]+1, donc la valeur d'ajustement de Heap la complexité est O(logn), et la boucle externe a f(n) fois, donc la complexité finale est O(nlogn).
Heap est principalement utilisé pour implémenter une file d'attente prioritaire :
Le système d'exploitation de manière dynamique. sélectionne la priorité d'exécution de la mission suprême.
Dans un problème statique, sélectionnez les M premiers noms parmi N éléments. La complexité de l'utilisation du tri : O(NlogN) et la complexité de l'utilisation de la file d'attente prioritaire : O(NlogM).
Les différentes complexités de la mise en œuvre de files d'attente prioritaires à l'aide de tableaux ordinaires, de tableaux séquentiels et de tas sont les suivantes :
Utiliser des tas pour implémenter Les files d'attente prioritaires peuvent rendre la complexité d'entrée et de sortie de la file d'attente très faible.
Ce qui précède représente l'intégralité du contenu de cet article. J'espère qu'il sera utile à l'étude de chacun. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois !
Recommandations associées :
JS implémente le tri par fusion
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!