La clasificación del montón se divide en dos procesos:
1. Construye una pila.
El montón es esencialmente un árbol completamente binario y debe cumplir con lo siguiente: las palabras clave de cualquier nodo no hojado en el árbol no son mayores que (o no menos que) las palabras clave del niño (si hay) el nodo.
El montón se divide en: un montón de raíz grande y un pequeño montón de raíz. El orden ascendente se usa para clasificar un montón de raíz grande, y el orden descendente se usa para clasificar un montón de raíz pequeño.
Si se trata de un montón de raíz grande, el nodo con el valor más grande se ajusta a la raíz del montón ajustando la función.
2. Guarde la raíz del montón en la cola y llame a la función de ajuste para la secuencia restante. Una vez completado el ajuste, guarde el seguidor máximo en la cola -1 (-1, -2, ..., -i), y luego ajuste la secuencia restante y repita el proceso hasta que se complete la clasificación.
La copia del código es la siguiente:
// ajustar la función
function HeadAdJust (Elements, pos, len) {
// Guardar el valor del nodo actual
var swap = elements [pos];
// localizar el nodo infantil a la izquierda del nodo actual
var niño = pos * 2 + 1;
// recursivo hasta que no haya hijos
while (niño <len) {
// Si el nodo actual tiene un nodo infantil en la derecha y el nodo infantil correcto es más grande, use el nodo infantil correcto
// Comparar con el nodo actual
if (Child + 1 <Len && Elements [Child] <Elements [Child + 1]) {
niño += 1;
}
// Compare el nodo actual con el nodo infantil más grande, si el valor es menor que, realice un intercambio de valor y ubique el nodo actual después del intercambio
// en el nodo infantil
if (elements [pos] <elements [niño]) {
elementos [pos] = elementos [niño];
pos = niño;
niño = Pos * 2 + 1;
}
demás{
romper;
}
elementos [pos] = swap;
}
}
// construir el montón
función buildHeap (elementos) {
// Comience desde el último nodo con el nodo infantil, compare el nodo con su nodo infantil,
// Después de intercambiar el número más grande con este nodo, el mismo proceso de intercambio se realiza al nodo delantero a su vez.
// Hasta que se construya un montón superior grande (el orden ascendente es una parte superior grande, el orden descendente es pequeño)
para (var i = Elements.length/2; i> = 0; i-) {
HeadAdJust (Elements, I, Elements.length);
}
}
sort de función (elementos) {
// construir el montón
BuildHeap (elementos);
// ajustar desde el final de la secuencia
para (var i = Elements.length-1; i> 0; i-) {
// La parte superior de la pila es siempre el elemento más grande, por lo que se intercambiará la parte superior de la pila y el elemento de cola.
// El elemento máximo se guarda al final y no participa en ajustes posteriores
var swap = elements [i];
Elementos [i] = Elements [0];
elementos [0] = intercambio;
// Hacer ajustes, ajuste el elemento máximo en la parte superior del montón
HeadAdJust (elementos, 0, i);
}
}
Elementos var = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log ('antes:' + elementos);
ordenar (elementos);
console.log ('After:' + elements);
eficiencia:
Complejidad del tiempo: mejor: o (nlog2n), peor: o (nlog2n), promedio: o (nlog2n).
Complejidad del espacio: O (1).
Estabilidad: inestable