Le tri du tas est divisé en deux processus:
1. Construisez une pile.
Le tas est essentiellement un arbre complètement binaire et doit répondre à ce qui suit: Les mots clés de tout nœud non-feuille de l'arborescence ne sont pas supérieurs à (ou pas moins) les mots clés de l'enfant (s'il y en a) le nœud.
Le tas est divisé en: un grand tas de racine et un petit tas de racine. L'ordre croissant est utilisé pour trier un grand tas de racine, et l'ordre descendant est utilisé pour trier le petit tas de racine.
S'il s'agit d'un grand tas de racine, le nœud avec la plus grande valeur est ajusté à la racine du tas en ajustant la fonction.
2. Enregistrez la racine du tas à la queue et appelez la fonction de réglage de la séquence restante. Une fois le réglage terminé, enregistrez le suiveur maximum à la queue -1 (-1, -2, ..., -i), puis ajustez la séquence restante et répétez le processus jusqu'à ce que le tri soit terminé.
La copie de code est la suivante:
// ajuste la fonction
fonction têtedjuste (éléments, pos, len) {
// Enregistrer la valeur actuelle du nœud
var swap = éléments [pos];
// Localisez le nœud enfant à gauche du nœud actuel
var child = pos * 2 + 1;
// récursif jusqu'à ce qu'il n'y ait pas d'enfants
tandis que (enfant <len) {
// Si le nœud actuel a un nœud enfant à droite et que le bon nœud enfant est plus grand, utilisez le bon nœud enfant
// Comparez avec le nœud actuel
if (child + 1 <len && elements [child] <elements [enfant + 1]) {
Enfant + = 1;
}
// Comparez le nœud actuel avec le nœud enfant le plus grand, si la valeur est inférieure, effectuez un échange de valeur et localisez le nœud actuel après l'échange
// sur le nœud enfant
if (éléments [pos] <éléments [enfant]) {
éléments [pos] = éléments [enfant];
pos = enfant;
Enfant = pos * 2 + 1;
}
autre{
casser;
}
éléments [pos] = swap;
}
}
// Construisez le tas
fonction buildheap (éléments) {
// commence à partir du dernier nœud avec le nœud enfant, comparez le nœud avec son nœud enfant,
// Après avoir échangé le plus grand nombre avec ce nœud, le même processus d'échange est effectué à son tour au nœud avant.
// jusqu'à ce qu'un grand tas de tas soit construit (l'ordre croissant est un grand haut, l'ordre descendant est petit en haut)
for (var i = elements.length / 2; i> = 0; i -) {
headadjuste (éléments, i, elements.length);
}
}
Fonction Sort (éléments) {
// Construisez le tas
buildheap (éléments);
// ajuster à partir de la fin de la séquence
for (var i = elements.length-1; i> 0; i -) {
// Le haut de la pile est toujours le plus grand élément, donc le haut de la pile et l'élément de queue seront échangés.
// L'élément maximum est enregistré à la fin et ne participe pas aux ajustements ultérieurs
var swap = éléments [i];
éléments [i] = éléments [0];
éléments [0] = swap;
// effectuez des ajustements, ajustez l'élément maximum en haut du tas
tête-à-tête (éléments, 0, i);
}
}
Var Elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log ('avant:' + éléments);
Trier (éléments);
Console.log ('After:' + Elements);
efficacité:
Complexité temporelle: meilleur: o (nlog2n), pire: o (nlog2n), moyenne: o (nlog2n).
Complexité de l'espace: O (1).
Stabilité: instable