1. Eu tenho que falar sobre árvores binárias
Para entender a pilha, você deve primeiro entender a árvore binária. Na ciência da computação, uma árvore binária é uma estrutura de árvore com no máximo duas subárvores por nó. Geralmente, as subárvores são chamadas de "subárvore esquerda" e "subárvore direita". As árvores binárias são frequentemente usadas para implementar árvores de pesquisa binária e montes binários.
Cada nó de uma árvore binária possui no máximo duas subárvores (nós com graus maiores que 2). As subáridas de uma árvore binária podem ser divididas na esquerda e à direita, e a ordem não pode ser revertida. A i -ésima camada da árvore binária possui no máximo 2i - 1 nó; A árvore binária com uma profundidade de k tem no máximo 2k - 1 nó; Para qualquer árvore binária T, se o número de nós terminais for N0 e o número de nós com um grau de 2 for N2, n0 = n2 + 1.
Existem três diferenças principais entre uma árvore e uma árvore binária:
O número de nós na árvore é de pelo menos 1, enquanto o número de nós na árvore binária pode ser 0.
Não há limite para o grau máximo de nós na árvore, enquanto o grau máximo de nós na árvore binária é 2
Não há diferença entre a esquerda e a direita nos nós de uma árvore, enquanto não há diferença entre a esquerda e a direita nos nós de uma árvore binária.
Árvores binárias são divididas em árvores binárias completas e árvores binárias completas.
Árvore binária completa: uma árvore com uma profundidade de k e tem 2k - 1 nó é chamado de árvore binária completa
(Árvore binária completa com profundidade 3)
Árvore binária completa: uma árvore binária com n nós com profundidade k. É chamado de árvore binária completa se e somente se cada um de seus nós corresponder a um nó com números de sequência de 1 a n em uma árvore binária completa com profundidade k.
(Árvore binária completa com profundidade 3)
2. O que é um monte?
Uma pilha (pilha binária) pode ser considerada uma árvore binária completa. Uma propriedade "excelente" de uma árvore binária completa é que, exceto a camada inferior, cada camada está cheia, o que permite que a pilha seja representada por uma matriz (as árvores binárias gerais comuns são geralmente representadas por listas vinculadas como contêineres básicos) e cada nó corresponde a um elemento na matriz.
A figura a seguir mostra a relação entre uma pilha e uma matriz
(A relação entre heap e matriz)
Para o subscrito i de um nó, ele pode ser facilmente calculado para o subscrito do nó pai e do nó filho deste nó:
Pai (i) = piso (i/2), o subscrito do nó pai de i
Esquerda (i) = 2i, o subscrito do nó infantil esquerdo de i
Certo (i) = 2i + 1, o subscrito certo do nó filho de i
Geralmente, existem dois tipos de montes binários: a maior pilha e a menor pilha.
Heap máximo:
O valor máximo do elemento na pilha máxima aparece no nó raiz (parte superior da pilha)
O valor do elemento de cada nó pai na pilha é maior ou igual ao seu nó filho (se existir)
(Heap máximo)
Heap mínimo:
O valor mínimo do elemento na pilha mínima aparece no nó raiz (topo da pilha)
O valor do elemento de cada nó pai na pilha é menor ou igual ao seu nó filho (se existir)
(Pilha mínima)
3. Princípio da classificação de heap
A classificação da pilha é retirar o número máximo na parte superior da pilha máxima, continuar ajustando a pilha restante na pilha máxima e retire o número máximo na parte superior da pilha novamente. Esse processo continua até que haja apenas um número restante. Defina as seguintes operações na pilha:
Max-heapify: ajuste o nó final da pilha para que o nó filho seja sempre menor que o nó pai
Crie um heap
HEAP-SORT: Remova o nó raiz dos primeiros dados e execute a operação recursiva do ajuste máximo da pilha
Antes de continuar a discussão a seguir, uma questão que precisa ser observada é: as matrizes são todas baseadas em zero, o que significa que nosso modelo de estrutura de dados de heap mudará.
(Baseado em zero)
Da mesma forma, várias fórmulas de cálculo também devem ser ajustadas de acordo:
Pai (i) = piso ((i-1)/2), o subscrito do nó pai de i
Esquerda (i) = 2i + 1, o subscrito do nó infantil esquerdo de i
Certo (i) = 2 (i + 1), o subscrito certo do nó filho de i
A função do ajuste máximo da pilha (MaxHeapify) é manter as propriedades da maior pilha e é a sub -rotina principal para criar a maior pilha. O processo de operação é mostrado na figura:
(Max-heapify)
Como a pilha ainda viola a natureza da pilha após um ajuste, é necessário um teste recursivo para que todo o heap atenda à natureza da pilha. Pode ser expresso em JavaScript da seguinte forma:
/** * Verifique no índice e mantenha as propriedades máximas da pilha * * @Array * * o índice de partida da verificação @Index * * @HeapSize Size **/função maxheapify (Array, Index, Heapsize) {var iMax = Índice, Ileft = 2 * Índice + 1, Irright = 2 * (index + 1); if (iLeft <heapsize && Array [index] <Array [ileft]) {iMax = iLeft; } if (irright <heapsize && Array [IMAX] <Array [IRIGHT]) {IMAX = IRIGHT; } if (iMax! = index) {swap (matriz, IMAX, index); maxheapify (Array, IMAX, Heapsize); // ajuste recursivo}} swap (matriz, i, j) {var temp = array [i]; Array [i] = Array [J]; Array [j] = temp;}De um modo geral, a recursão é usada principalmente no método de divisão e tratamento, e não há necessidade de divisão e tratamento aqui. Além disso, chamadas recursivas requerem prensagem/limpeza da pilha, que tem uma ligeira desvantagem no desempenho em comparação com a iteração. Obviamente, isso pode ser ignorado de acordo com a regra 20/80. Mas se você acha que usar a recursão fará com que você se sinta desconfortável, também pode usar a iteração, como a seguinte:
/** * Verifique no índice e mantenha as propriedades máximas da heap * * @Array * * o índice inicial da verificação @Index * * @HeapSize Size **/função maxheapify (Array, Index, Heapsize) {var iMax, iLeft, irright; while (true) {iMax = index; Ileft = 2 * Índice + 1; IRIGHT = 2 * (índice + 1); if (iLeft <heapsize && Array [index] <Array [ileft]) {iMax = iLeft; } if (irright <heapsize && Array [IMAX] <Array [IRIGHT]) {IMAX = IRIGHT; } if (iMax! = index) {swap (matriz, IMAX, index); índice = IMAX; } else {break; }}} Swap de função (Array, i, j) {var temp = array [i]; Array [i] = Array [J]; Array [j] = temp;}O objetivo de criar uma pilha máxima (Build-Max-Heap) é transformar uma matriz em uma pilha máxima, aceitando dois parâmetros de matriz e tamanho da pilha. O Build-Max-Heap chamará Max-Heapify de baixo para cima para transformar a matriz e construir a pilha máxima. Como o Max-Heapify pode garantir que os nós após a inscrição eu atendam às propriedades da maior pilha, a chamada de baixo para cima para Max-Heapify pode manter essa propriedade durante o processo de transformação. Se o elemento de número máximo de heap for n, o Build-Max-Heap chamará max-heapify na sequência do pai (n). O processo é o seguinte:
A descrição é a seguinte no JavaScript:
função BuildMaxHeap (Array, Heapsize) {var i, iparent = math.floor ((heapsize - 1) / 2); para (i = iparent; i> = 0; i--) {maxheapify (array, i, heapsize); }}HEAP-SORT é o algoritmo de interface para classificação de heap. Primeiro, o HEAP-Sort chama Build-Max-Heap para transformar a matriz na pilha máxima, depois troca os elementos superior e inferior da pilha, depois levanta a parte inferior e finalmente chama Max-Heapify para manter as propriedades máximas da pilha. Como o elemento superior da pilha deve ser o maior elemento da pilha, após uma operação, o maior elemento presente na pilha é separado da pilha da pilha e, após repetidas vezes N-1, a matriz é organizada. Todo o processo é o seguinte:
A descrição é a seguinte no JavaScript:
function heapsort (array, heapsize) {BuildMaxHeap (Array, Heapsize); para (int i = heapsetize-1; i> 0; i--) {swap (array, 0, i); maxheapify (matriz, 0, i); }}4. Implementação de idiomas JavaScript
Finalmente, organize o acima em código JavaScript acima da seguinte maneira:
function heapsort (array) {swap function (array, i, j) {var temp = array [i]; Array [i] = Array [J]; matriz [j] = temp; } função maxheapify (array, índice, heapsize) {var iMax, ileft, irright; while (true) {iMax = index; Ileft = 2 * Índice + 1; IRIGHT = 2 * (índice + 1); if (iLeft <heapsize && Array [index] <Array [ileft]) {iMax = iLeft; } if (irright <heapsize && Array [IMAX] <Array [IRIGHT]) {IMAX = IRIGHT; } if (iMax! = index) {swap (matriz, IMAX, index); índice = IMAX; } else {break; }}} função BuildMaxHeap (Array) {var i, iparent = math.floor (array.length / 2) - 1; para (i = iparent; i> = 0; i--) {maxheapify (matriz, i, array.length); }} função classy (Array) {BuildMaxHeap (Array); for (var i = array.length-1; i> 0; i--) {swap (matriz, 0, i); maxheapify (matriz, 0, i); } retornar a matriz; } retornar classificar (array);}5. Aplicação do algoritmo de classificação de heap
(1) Desempenho/complexidade do algoritmo
A complexidade do tempo da classificação de heap é muito estável (podemos ver que não é sensível aos dados de entrada) e é a complexidade O (NN), o melhor caso é o mesmo que o pior caso.
No entanto, sua complexidade espacial varia de acordo com a implementação. O acima discute duas complexidades comuns: O (n) e O (1). Com base no princípio de salvar espaço, recomendo o método de complexidade O (1).
(2) Estabilidade do algoritmo
Há um grande número de processos de filtragem e movimento na classificação de heap, que pertencem a um algoritmo de classificação instável.
(3) Cenário aplicável ao algoritmo
A classificação da pilha incorrerá em uma sobrecarga relativamente grande no processo de construção da pilha e ajuste a pilha, e não é aplicável quando há poucos elementos. No entanto, quando há muitos elementos, ainda é uma boa escolha. Especialmente ao resolver problemas como "o número de principais n grandes", é quase o algoritmo preferido.