1. Conhecimento básico
O que geralmente chamamos de pilha refere -se a uma pilha binária, que também é chamada de árvore binária completa ou uma árvore binária aproximadamente completa. A pilha binária é dividida na maior pilha e na menor pilha.
A classificação de heap refere -se a um algoritmo de classificação projetado usando a estrutura de dados da heap, que é um tipo de seleção de classificação. Você pode localizar rapidamente elementos do índice especificado usando as características da matriz. As matrizes podem obter diretamente elementos com base no índice, e a complexidade do tempo é O (1), ou seja, constantes, portanto são extremamente eficientes para a aquisição de valor.
As características da pilha máxima são as seguintes:
As características da pilha mínima são as seguintes:
2. Pensamento do algoritmo
1. A idéia do algoritmo da maior pilha é:
Primeiro, o R [0… n-1] inicial é incorporado no maior heap. Neste momento, é uma pilha não ordenada. O topo da pilha é o maior elemento e, em seguida, o último recorde R [n-1] da área não ordenada é trocada. Isso resulta na nova área não ordenada r [0… n-2] e na área ordenada r [n-1] e satisfaz r [0… n-2] .Keys ≤ r [n-1] .Key
Como o primeiro r [0… n-2] pode não satisfazer as propriedades da pilha máxima após a troca, o primeiro r [0… n-2] é ajustado à pilha máxima até que apenas o último elemento de r [0] seja ajustado.
Após a conclusão da classificação máxima da pilha, é na verdade uma sequência ascendente. Cada vez que a pilha é ajustada, o maior elemento é obtido e trocado com o último elemento da pilha atual. Portanto, a sequência final obtida é uma sequência ascendente.
2. A idéia do algoritmo da menor pilha é:
Primeiro, o R [0… n-1] inicial é incorporado na menor pilha. Neste momento, é uma pilha não ordenada. O elemento superior da pilha é o menor elemento e troca o top r [0] com o último r [n-1] da área não ordenada, obtendo assim o novo heap r ordenado [0… n-2] e o heap r [n-1] e satisfazendo r [0… n-2] .keys> = r [n-1].
Como o primeiro r [0… n-2] pode não atender às propriedades da pilha mínima após a troca, o primeiro r [0… n-2] é ajustado à pilha mínima até que apenas o último elemento de r [0] seja ajustado e a pilha mínima seja classificada. Após a solicitação da pilha mínima, é na verdade uma sequência descendente. Cada vez que a pilha é ajustada, o menor elemento é obtido e depois trocado com o último elemento da pilha não ordenada atual, de modo que a sequência obtida está em ordem decrescente.
Dica: o processo de classificação de heap é na verdade o processo de expansão continuamente da área ordenada e, em seguida, reduzindo continuamente a área desordenada até que haja apenas áreas ordenadas.
3. Análise do processo de classificação
Como o algoritmo é relativamente abstrato, aqui ilustramos diretamente o processo de classificação de heap, dando um pequeno exemplo. Em seguida, usamos essa sequência não ordenada para usar a maior pilha para classificação de heap, e a sequência resultante é a sequência ascendente (ASC).
Sequência não ordenada: 89, -7,999, -89,7,0, -888,7, -7
Etapa 1: Inicialize a pilha máxima para construir:
Etapa 2: Troca o elemento máximo 999 na parte superior da pilha com o último elemento da área não ordenada, para que 999 se torne uma área ordenada. Após a troca, -7 se torna o topo da pilha. Como -7 não é o maior elemento na área não ordenada, é necessário ajustar a área não ordenada, de modo que o valor máximo 89 na área não ordenada se torne o topo da pilha, então -7 e 89 são trocados. Após a troca, a subárvore direita de 89 não atende às propriedades da maior pilha; portanto, a subárvore direita deve ser ajustada à maior pilha, então -7 deve ser trocada com 0, como mostrado na figura abaixo:
A partir da figura, quando -7% de 89%, a parte superior da pilha é o maior elemento, mas o filho esquerdo de -7 é 0 e a criança certa é -888. Como -7 <0, o nó -7 não atende às propriedades da pilha, por isso precisa ser ajustado. Então, 0 é trocado com -7.
Em seguida, repita o segundo passo até que se torne uma área ordenada.
Finalmente: o que é obtido é uma sequência ascendente
4. Complexidade do tempo
O tempo de classificação de heap é composto principalmente da sobrecarga de tempo de estabelecer a pilha inicial e ajustar repetidamente a pilha. Como a classificação da pilha é instável, a complexidade do tempo que obtém será maior de acordo com a situação real, portanto, só pode levar a complexidade média do tempo.
A complexidade média do tempo é: o (n * log2 (n))
As operações demoradas da classificação de heap incluem: heap inicial + ajuste repetido da pilha, e a complexidade do tempo é a seguinte:
1. Construção inicial de heap: Cada nó pai comparará e trocará com os nós da criança esquerda e direita por até 2 vezes, portanto a complexidade está relacionada ao número de nós pais. Com base em 2x <= n (x é o número de vezes que n elementos podem ser dobrados ao meio, ou seja, o número de nós pais), ele é obtido x = log2n. Isto é, o (log2n)
2. Ajuste repetido da pilha: Como os resultados da comparação da matriz são registrados durante a inicialização da pilha, o tipo de heap não é sensível à ordem da matriz da sequência original e a melhor situação é semelhante ao pior dos casos. O elemento superior da pilha precisa ser extraído N-1 vezes. Cada vez que o elemento superior da heap é obtido, o heap precisa ser reconstruído (O (reconstruir heap) <O (heap inicial)). Tão menos que o (n-1) * o (log2n)
Uso recomendado:
Como o número de vezes a inicialização do heap precisa ser comparada, a classificação de heap é mais adequada para situações em que a quantidade de dados é muito grande (milhões de dados ou mais). Como a classificação rápida eficiente é baseada na implementação recursiva, ocorre um erro de transbordamento de pilha quando o volume de dados é muito grande.
5. Código de amostra Java
classe pública heapsort {private static int [] classy = new int [] {1,0,10,20,3,5,6,4,9,8,12, 17,34,11}; public static void main (string [] args) {BuildMaxHeApify (Sort); heapsort (classificação); imprimir (classificar); } private estático void BuildMaxHeApify (int [] dados) {// Somente aqueles sem filhos precisam criar o heap máximo, inicie a partir do último nó pai int startIndex = getParentIndex (data.length-1); // crie o peso máximo a partir do final e é o heap correto para (int i = startIndex; i> 0; }} / ***Crie o heap máximo**@paramdata*@paramheapSize requer o tamanho da pilha máxima, que geralmente é usada na classificação, porque o valor máximo é colocado no final, o final não é mais classificado como o ponto de vista máximo, maix maix* índice) {// Compare o ponto atual com os nós da criança esquerda e direita int esquerd = getChildLeftIndex (index); int correto = getChildRightIndex (índice); int maior = índice; if (esquerda <heapsize && data [index] <data [esquerda]) {maior = esquerda; } if (direita <heapsize && data [maior] <data [direita]) {maior = certo; } // Depois de obter o valor máximo, pode precisar ser trocado. Se trocados, seus filhos podem não ser o maior heap. Ele precisa ser reajustado se (maior! = Índice) {int temp = dados [index]; dados [index] = dados [maior]; dados [maior] = temp; maxheapify (dados, heapsize, maior); }} /***Classificação, o valor máximo é colocado no final. Embora os dados sejam a maior pilha, ele se torna incremental após a classificação * *@paramdata */private estático vazio heapsort (int [] dados) {// troca com o cabeçalho no final, ajuste o heap máximo após troca (int i = data.length-1; i> 0; i-) {int temep = dados [0]; dados [0] = dados [i]; dados [i] = temp; maxheapify (dados, i, 0); }} / ** *paramCurrent *@return * / private static int getParentIndex (int current) {return (atual-1) >> 1; } / ** *Apresentar a posição do nó da criança preste atenção aos parênteses, e a prioridade de adição é maior * *@paramCurrent *@return * / private static int getChildleftIndex (int current) {return (atual << 1) +1; } / * * } private estático void print (int [] dados) {int pre = -2; for (int i = 0; i <data.length; i ++) {if (pre <(int) getLog (i+1)) {pre = (int) getLog (i+1); System.out.println (); } System.out.print (dados [i]+"|"); }}/** *logo com base 2 * *@paraparam *@return */private estático duplo getLog (param duplo) {return math.log (param) /math.log (2); }}