As propriedades da pilha
Uma pilha é uma árvore completamente binária, que pode ser implementada na realidade através de uma matriz. Uma de suas propriedades mais importantes é que qualquer nó é menor que (maior que) é igual a seus nós filhos. A pilha com o menor nó da raiz é chamada de menor heap, e a pilha com o maior nó raiz é chamada de maior monte. A figura a seguir mostra um exemplo de uma maior pilha e sua representação da matriz, que pode ser visto intuitivamente que cada nó é maior que seus filhos.
Como pode ser visto na figura acima, os nós de uma árvore completamente binária podem ser organizados em ordem a partir do nó raiz número 1, correspondendo ao índice na matriz A (observe que o subscrito aqui começa a partir de 1). Dado um nó I, podemos facilmente obter seu filho esquerdo é 2i, o filho direito é 2i+1 e o nó pai é i/2
Operações básicas de heap
Existem duas operações básicas para a pilha (consulte a pilha mínima como exemplo abaixo):
Insira o elemento K: Adicione K diretamente ao final da matriz e depois borbulhe para ajustar a pilha. Operação de bolhas: Compare o elemento a ser ajustado ao nó pai e, se for maior que o nó pai, troque até que as propriedades da pilha sejam restauradas.
Extraia o maior valor: o maior valor é o elemento raiz. Em seguida, exclua-o, deixe o elemento raiz = o último elemento do nó da folha e depois borbulhar do elemento raiz para ajustar a pilha. Operação para baixo da bolha: Cada vez, você deve selecionar o menor nó da criança dos três nós para ajustar o nó, que tem as crianças esquerda e direita para trocar (se o menor, não precisa se trocar), até que as propriedades da pilha sejam restauradas.
Na prática, geralmente é necessário construir uma matriz não ordenada contendo n elementos em montes. O construtor na classe Heap abaixo mostrará como construir uma pilha através do ajuste para baixo da bolha _bubbledown. A pilha é essencialmente uma árvore completamente binária e a altura da árvore é sempre lognlogn. A operação demorada de cada operação básica é borbulhar e se ajustar para atender às propriedades da pilha, de modo que sua complexidade de tempo é O (nLogn) O (nlogn).
Exemplo Java:
// Float public void Swim (int k) {while (k/2> = 1 && Less (pq [k/2], pq [k])) {Excc (pq, k/2, k); k = k/2; }} // afundar private void sink () {int k = 1; while (2*k <n) {int j = 2*k; if (menos (pq [j], pq [j+1])) j ++; if (menos (PQ [k], pq [j])) Exch (PQ, K, J); mais quebrar; k = j; }} Princípio de implementação de classificação de heap
É dividido em duas etapas:
1. Organize as matrizes em ordem binária
2. Altere a posição do nó raiz e do último nó e afunde o nó raiz.
concluir:
Talvez meu código seja um pouco diferente da animação acima, mas os princípios básicos são semelhantes.
classe pública heapsort estende basesort {private int n; @Override public void Sort (comparável [] a) {n = A.Length-1; int k = n/2; while (k> = 1) {pia (a, k); k--; } k = 1; while (k <= n) {Excc (a, k, n--); pia (a, k); }}}