A classificação de heap é dividida em dois processos:
1. Construa uma pilha.
O heap é essencialmente uma árvore completamente binária e deve atender ao seguinte: As palavras-chave de qualquer nó não folhas na árvore não são maiores que (ou não menos que) as palavras-chave da criança (se houver) o nó.
A pilha é dividida em: uma grande pilha de raiz e uma pequena pilha de raiz. A ordem ascendente é usada para classificar uma grande pilha de raiz e a ordem descendente é usada para classificar a pilha de raiz pequena.
Se for uma pilha de raiz grande, o nó com o maior valor é ajustado à raiz da pilha ajustando a função.
2. Salve a raiz da pilha na cauda e chame a função de ajuste para a sequência restante. Após a conclusão do ajuste, salve o seguidor máximo na cauda -1 (-1, -2, ..., -i) e ajuste a sequência restante e repita o processo até que a classificação seja concluída.
A cópia do código é a seguinte:
// ajuste a função
function headadjust (elementos, pos, len) {
// salve o valor do nó atual
var swap = elementos [POS];
// Localize o nó filho à esquerda do nó atual
var criança = pos * 2 + 1;
// recursivo até que não haja filhos
while (criança <len) {
// Se o nó atual tiver um nó infantil à direita e o nó infantil certo for maior, use o nó infantil certo
// Compare com o nó atual
if (criança + 1 <len && elements [filho] <elementos [filho + 1]) {
criança += 1;
}
// Compare o nó atual com o maior nó infantil, se o valor for menor que, execute a troca de valor e localize o nó atual após a troca
// No nó infantil
if (elementos [pos] <elementos [filho]) {
elementos [pos] = elementos [filho];
pos = criança;
criança = pos * 2 + 1;
}
outro{
quebrar;
}
elementos [pos] = troca;
}
}
// Construa a pilha
função BuildHeap (elementos) {
// Comece do último nó com o nó filho, compare o nó com seu nó filho,
// Depois de trocar o maior número com este nó, o mesmo processo de troca é realizado no nó frontal por sua vez.
// Até que uma pilha superior grande seja construída (a ordem ascendente é grande, a ordem descendente é pequena)
for (var i = elements.length/2; i> = 0; i-) {
hitnjust (elementos, i, elementos.length);
}
}
Função classificar (elementos) {
// Construa a pilha
BuildHeap (elementos);
// ajuste do final da sequência
for (var i = elements.length-1; i> 0; i-) {
// A parte superior da pilha é sempre o maior elemento, portanto a parte superior da pilha e o elemento da cauda serão trocados.
// O elemento máximo é salvo no final e não participa dos ajustes subsequentes
var swap = elementos [i];
elementos [i] = elementos [0];
elementos [0] = troca;
// Faça ajustes, ajuste o elemento máximo na parte superior da pilha
hitcaltjust (elementos, 0, i);
}
}
var elementos = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log ('antes:' + elementos);
classificar (elementos);
console.log ('depois:' + elementos);
eficiência:
Complexidade do tempo: melhor: o (nlog2n), pior: o (nlog2n), média: o (nlog2n).
Complexidade do espaço: o (1).
Estabilidade: instável