A pilha é uma estrutura importante na estrutura de dados. Depois de entender o conceito e a operação de "heap", você pode dominar rapidamente a classificação de heap.
O conceito de pilha
Heap é uma árvore binária completa especial. Se os valores de todos os nós de uma árvore completamente binária não forem menores que seus filhos, isso é chamado de grande monte de raiz (ou monte superior grande); Se os valores de todos os nós não forem maiores que seus filhos, ele é chamado de pilha de raiz pequena (ou pequena pilha superior).
Em uma matriz (armazenando o nó raiz no número do subscrito 0), é fácil obter a seguinte equação (essas duas equações são muito importantes):
1. O nó com subscrito é I e as coordenadas do nó pai são (I-1)/2;
2. O nó com subscrito é I, as coordenadas do nó da criança esquerda são 2*i+1 e o nó filho direito é 2*i+2.
Estabelecimento e manutenção da pilha
O heap pode suportar várias operações, mas agora nos preocupamos apenas com duas questões:
1. Dada uma matriz não ordenada, como construí -la como uma pilha?
2. Depois de excluir o elemento superior da pilha, como ajustar a composição a uma nova pilha?
Vejamos a segunda pergunta primeiro. Suponha que já tenhamos uma pilha de raiz grande pronta. Agora excluímos o elemento raiz, mas não movemos os outros elementos. Pense no que aconteceu: o elemento raiz está vazio, mas os outros elementos ainda mantêm as propriedades da pilha. Podemos mover o último elemento (nome do código A) para a posição do elemento raiz. Se não for um caso especial, as propriedades da pilha são destruídas. Mas isso ocorre simplesmente porque A é menor que um de seus elementos filhos. Portanto, podemos trocar um e esse elemento filho para a posição. Se A for maior do que todos os seus elementos filhos, a pilha será ajustada; Caso contrário, repita o processo acima, o elemento A continua a "afundar" na estrutura da árvore até que seja apropriado e a matriz restaura as propriedades da pilha. O processo acima é geralmente chamado de "triagem" e a direção é obviamente de cima para baixo.
Isso é verdade ao excluir um elemento, e o mesmo acontece com um novo elemento. A diferença é que colocamos o novo elemento no final e o comparamos com o nó pai, ou seja, filtá -lo de baixo para cima.
Então, como resolver o primeiro problema?
Muitos dos livros sobre estruturas de dados que li estão se filtrando do primeiro nó não folhas até que o elemento raiz seja filtrado. Este método é chamado de "método de filtragem", que requer elementos de filtragem de loop N/2.
Mas também podemos aprender com a idéia de "criar algo do nada". Podemos considerar o primeiro elemento como uma pilha e, em seguida, adicionar constantemente novos elementos a ele. Este método é chamado de "método de inserção", que requer inserção de loop de elementos (N-1).
Como o método de filtragem e o método de inserção são diferentes, os montes que criam geralmente são diferentes para os mesmos dados.
Depois de um entendimento difícil da pilha, a classificação da pilha é uma coisa natural.
Visão geral do algoritmo/idéias
Precisamos de uma sequência ascendente, o que devemos fazer? Podemos construir uma pilha mínima e, em seguida, emitir o elemento raiz a cada vez. No entanto, esse método requer espaço extra (caso contrário, causará muito movimento de elementos, e sua complexidade subirá a O (n^2)). E se precisarmos de classificação no local (ou seja, não há complexidade espacial O (n) permitida)?
Existe um caminho. Podemos construir a pilha máxima e, em seguida, produzimos o valor máximo na última posição e o segundo valor máximo na última posição ... Como a saída máxima do elemento cada vez liberará o primeiro espaço, podemos apenas colocar esse elemento sem precisar de espaço extra. Ideia muito bonita, certo?
classe pública heapsort {public static void main (string [] args) {int [] arr = {50, 10, 90, 30, 70, 40, 80, 60, 20}; System.out.println ("Antes de classificar:"); for (int i = 0; i <arr.length; i ++) {System.out.print (arr [i]+""); } // Heap Satinging HeapSort (ARR); System.out.println (); System.out.println ("Após a classificação:"); for (int i = 0; i <arr.length; i ++) {System.out.print (arr [i]+""); }} / *** Classificação de heap* / private estático void HeapSort (int [] arr) {// Construa a sequência a ser classificada em um grande heap top para (int i = arr.length / 2; i> = 0; i-) {heapjust (arr, i, arr.ngth); } // Troque gradualmente o nó raiz de cada valor máximo com o elemento final e ajuste a árvore binária para torná-la uma grande pilha superior para (int i = arr.length-1; i> 0; i--) {swap (arr, 0, i); // troca o recorde superior da heap com o último registro do heapjust subseqüente atualmente não classificado (arr, 0, i); // Após a troca, é necessário verifique se a pilha atende à grande pilha superior. Se não se encontrar, precisará ser ajustado}} / *** Processo de construção da matriz @Param Arr que precisa ser classificada* @param i o número do nó raiz do heap que precisa ser construído* @param n o comprimento da matriz* / private estático void heapjust (int [], int i, int i, int i, n) {n) {n) {Int N) {Int N). int pai; para (pai = arr [i]; leftChild (i) <n; i = criança) {Child = leftChild (i); // Se a subárvore esquerda for menor que a subárvore direita, você precisará comparar a subárvore direita com o nó pai se (filho! = N - 1 && arr [filho] <arr [filho+1]) {filho ++; // Aumente o número de série em 1, apontando para a subárvore direita} // se o nó pai for menor que o nó filho, você precisará trocar se (pai <arr [filho]) {arr [i] = arr [filho]; } else {break; // A grande estrutura de heap superior não é destruída, nenhum ajuste é necessário}} arr [i] = pai; } // Obtenha o nó do filho esquerdo privado estático int lesfild (int i) {return 2 * i + 1; } // Swap Posição da posição estática privada Swap (int [] arr, int index1, int index2) {int tmp = arr [index1]; arr [index1] = arr [index2]; arr [index2] = tmp; }}