Visão geral
A classificação de heap é uma classificação de seleção de árvores, que é uma melhoria eficaz na classificação direta da seleção.
A pilha é definida da seguinte forma: uma sequência de n elementos (k1, k2, ..., kn), se e somente se estiver satisfeito:
É chamado de pilha naquele momento. Como pode ser visto a partir da definição da pilha, o elemento superior da pilha (ou seja, o primeiro elemento) deve ser o menor item (Pequeno Heap Top) ou o maior item (grande heap superior).
Se uma pilha for armazenada em uma matriz unidimensional, a pilha corresponde a uma árvore completamente binária, e os valores de todos os nós não folhas (nós com crianças) não são maiores que (ou não menos que) os valores de seus filhos, e os valores do nó raiz (elemento superior do heap) são os menores (ou maiores).
(a) Grande sequência de heap superior: (96, 83, 27, 38, 11, 09)
(b) Sequência de heap Small Top Heap: (12, 36, 24, 85, 47, 30, 53, 91)
Inicialmente, a sequência de N números a serem classificados é considerada como uma árvore binária armazenada sequencialmente (árvore binária unidimensional de armazenamento de matriz), ajuste sua ordem de armazenamento para torná-lo um monte, emitir o elemento superior do heap para obter o menor (ou maior) elemento dos n elementos. Em seguida, reajuste os elementos N-1 restantes para se tornarem pilha, emitir o elemento superior da pilha e obter o elemento que é o segundo pequeno (ou o segundo grande) entre os n elementos. E assim por diante até que você finalmente obtenha uma sequência ordenada com N nós. Chame esse tipo de pilha de processo.
Etapas e exemplos
Existem dois problemas a serem resolvidos na implementação da classificação de heap:
(1) como construir n números a serem classificados em pilhas;
(2) Após a saída do elemento superior da pilha, como ajustar os elementos N-1 restantes para torná-lo uma nova pilha.
Construa o método Heap (Pequeno Heap Top):
O processo de construção de uma pilha para a sequência inicial é um processo de triagem repetida.
Uma árvore binária completa de n nós, então o último nó é a subárvore do nó N/2.
O filtro começa com a subárvore com o nó N/2º, pois a raiz (N/2 é o último nó com a subárvore), para que a subárvore se torne uma pilha.
Em seguida, filtre as subáridas com cada nó como raiz em sequência para a frente para torná -la uma pilha até o nó raiz.
Como mostrado na figura, a sequência desordenada do processo inicial de construção de uma pilha: (49, 38, 65, 97, 76, 13, 27, 49)
(a) Sequência não ordenada, árvore binária inicial, 97 (8/2 = 4 nó) é o nó pai do último nó (49).
(b) 97> = 49, substitua a posição e filtre o nó anterior 65 de N/2.
(c) 13 <= 27 e 65> = 13, substitua as posições de 65 e 13 e substitua 38 (ambos maiores que ele, nenhuma operação é necessária), filtro 49.
(d) 13 <= 38 e 49> = 13, substitua as posições de 49 e 13, 49> = 27, substitua as posições de 49 e 27.
(e) Finalmente, obtenha uma pilha, 13 é o número mínimo que obtemos.
Métodos para ajustar a pilha (Pequena heap superior):
É fornecido um monte de elementos M. Após a saída dos elementos superiores da pilha, os elementos M-1 são deixados. O elemento inferior da pilha é alimentado na parte superior da pilha e o heap é destruído, porque o nó raiz não atende às propriedades da pilha.
Trocar o nó raiz com elementos menores nas subárvores esquerda e direita.
Se trocado com a subárvore esquerda: se a pilha de subárvore esquerda estiver corrompida, repita o método (2).
Se trocado com a subárvore direita, repita o método (2) se a pilha da subárvore direita for destruída.
Continue executando a operação de troca acima em subáridas que não atendem às propriedades da pilha até que os nós da folha e a pilha sejam construídos.
Para ajustar a pilha, você só precisa considerar os nós corrompidos e outros nós não precisam ser ajustados.
Implementação de código (Java)
Execute o código e compare os comentários com as etapas de exemplo acima para comparação.
package com.coder4j.main;public class HeapSort { /** * Adjust to a small top heap (the result is from large to small after sorting) * * @param array is the heap array to be adjusted* @param s is the position of the array element to be adjusted* @param length is the length of the array * */ public static void heapAdjustS(int[] array, int s, int length) { int tmp = matriz [s]; Int Child = 2 * s + 1; // A posição do sistema de nó infantil esquerdo.out.println ("O nó a ser ajustado é: array [" + s + "] =" + tmp); Enquanto (criança <comprimento) {// criança + 1 é a criança certa atualmente ajustando o nó // se houver uma criança certa e for menor que a criança esquerda, use a criança direita para comparar com o nó, caso contrário, use a criança esquerda se (criança + 1 <comprimento && Array [filho]> array [filho + 1]) {criança ++; } System.out.println ("estará com a matriz infantil [" + filho + "] =" + matriz [filho] + "compare"); // se a criança menor for menor que este nó if (matriz [s]> Array [filho]) {System.out.println ("Child é menor que, posição de troca"); matriz [s] = matriz [filho]; // mova a criança menor para cima e substitua o nó atual a ser ajustado s = filho; // mova o nó ajustado para a posição original da matriz infantil mais jovem [filho] = tmp; criança = 2 * s + 1; // Continue julgando se o nó a ser ajustado precisa continuar a ser ajustado se (filho> = comprimento) {System.out.println ("Não há filhos, o ajuste acabou"); } else {System.out.println ("Continue comparando com o novo filho"); } // continuar; } else {System.out.println ("As crianças são mais antigas que elas, o ajuste acabou"); quebrar; // O nó atual a ser ajustado é menor que as crianças esquerda e direita, e não precisa ser ajustado, saia diretamente}}}/ ** * Ajuste para um pêlo superior grande (o resultado é de pequeno a amplo e a posição * * * * @param matric é a matriz de * * @param a posição * * * * * * * * * * * * * * * * heapadjustb (int [] matriz, int s, int length) {int tmp = matriz [s]; Int Child = 2 * s + 1; // A posição do sistema de nó infantil esquerdo.out.println ("O nó a ser ajustado é: array [" + s + "] =" + tmp); Enquanto (criança <comprimento) {// criança + 1 é a criança certa atualmente ajustando o nó // se houver uma criança certa e for maior que a criança esquerda, use a criança direita para comparar com o nó, caso contrário, use a criança esquerda se (criança + 1 <comprimento && Array [filho] <Array [filho + 1]) {criança ++; } System.out.println ("estará com a matriz infantil [" + filho + "] =" + matriz [filho] + "compare"); // Se a criança mais velha for maior que este nó se (Array [s] <Array [filho]) {System.out.println ("Child é maior que, posição de troca"); matriz [s] = matriz [filho]; // mova a criança mais velha para cima e substitua o nó atual a ser ajustado s = filho; // mova o nó ajustado para a posição original da matriz infantil mais antiga [filho] = tmp; criança = 2 * s + 1; // continue julgando se o nó a ser ajustado precisa ser ajustado se (filho> = comprimento) {System.out.println ("Não há filhos, o ajuste acabou"); } else {System.out.println ("Continue comparando com o novo filho"); } // continuar; } else {System.out.println ("As crianças são menores que elas, o ajuste acabou"); quebrar; // O nó atual a ser ajustado é maior que as crianças esquerda e direita e saia diretamente sem ajuste}}}/ ** * algoritmo de classificação de heap * * * @param Array * @param inverso true na ordem inversa, falsa em uma ordem positiva */ public static void Heaps (INT [] Array, boolean em NEVERSO) { 1) / 2, de modo a ajustar cada nó para cima para estar em conformidade com o sistema de heap.out.println ("Início inicial da pilha"); for (int i = (Array.Length-1) / 2; i> = 0; i-) {if (Inverse) {heapadjusts (matriz, i, Array.length); } else {heapadjustb (array, i, array.length); }} System.out.println ("End End Inicial"); for (int i = array.length-1; i> 0; i--) {// Troque o elemento superior H [0] e o último elemento no heap int tmp = matriz [i]; array [i] = array [0]; matriz [0] = tmp; // Após cada troca o elemento superior da pilha e o último elemento na pilha, o heap deve ser ajustado se (inverso) {heapAdjusts (matriz, 0, i); } else {heapadjustb (array, 0, i); }}} public static void main (string [] args) {int [] array = {49, 38, 65, 97, 76, 13, 27, 49}; heapsort (matriz, falso); para (int i: Array) {System.out.print (i + ""); }}}Resultados em execução:
The node to be adjusted at the beginning of the initial heap is: array[3] = 97 The child will be smaller with the child array[7] = 49 The child is smaller with the child, and the node to be adjusted at the end of the adjustment is: array[2] = 65 The child is smaller with the child array[5] = 13 The child is smaller with the child, and the node to be adjusted at the end of the adjustment is: Array [1] = 38 A criança é maior com a matriz infantil [3] = 49 A criança é maior com a matriz infantil [0] = 49 A criança é menor com a matriz infantil [2] = 13 A criança é menor com a matriz infantil [6] = 27 A criança é menor que a posição de troca e não há criança na posição de troca. O nó a ser ajustado após o ajuste é: matriz [0] = 97 A criança é menor que a criança. A criança é menor que a criança. A posição de troca continua a se comparar com o novo filho. A criança é a matriz [6] = 49 A criança é menor que a posição de troca e não há criança na posição de troca. O nó a ser ajustado após o ajuste é: matriz [0] = 97 A criança é menor que a criança. A criança é menor que a criança. A criança é menor que a criança. A criança é a matriz [1] = 38 A criança é menor que a criança. A criança é a matriz [3] = 49 A criança é menor que a criança. A criança é menor que a posição de troca. O nó a ser ajustado após o ajuste é: Array [0] = 65 A criança é a matriz [1] = 49 A criança é menor que a criança e a posição de troca continua sendo comparada com a nova criança. A criança será maior que a criança. O nó a ser ajustado após o ajuste é: matriz [0] = 76 A criança é maior que a criança. O nó a ser ajustado após o ajuste é: Array [0] = 76 A criança é menor que a criança. O nó a ser ajustado após o ajuste é: Array [0] = 49 A criança é menor que a criança. O nó a ser ajustado após o ajuste é: matriz [0] = 97 A criança é menor que a criança. O nó a ser ajustado após o ajuste é: Array [0] = 97 76 65 49 49 38 27 13 13
PS: a diferença entre classificação de heap e classificação de inserção direta
Na ordem de seleção direta, para selecionar o registro com a menor palavra-chave de R [1..n], a comparação N-1 deve ser realizada e, em seguida, selecione o registro com a menor palavra-chave em R [2..n], as comparações N-2 devem ser realizadas. De fato, nas seguintes comparações do N-2, muitas comparações podem ter sido feitas nas comparações anteriores do N-1, mas como esses resultados de comparação não foram retidos na ordem anterior, essas operações de comparação foram repetidas durante a próxima ordem.
A classificação de heap pode salvar parte dos resultados da comparação através de uma estrutura de árvore, que pode reduzir o número de comparações.