Heapify Time Complexity e a Linguagem C
O heap mínimo acima descreve uma pilha em que o número de crianças por nó dos pais pode ser mais de dois. Uma pilha binária é aquela em que o maior número de crianças por nó dos pais é dois. Uma pilha binária completa é aquela em que cada nó tem dois filhos, com a exceção de que, no nível mais baixo, pode haver apenas um nó de folha sem irmão; com o restante dos nós mais baixos de folhas emparelhados e começando da extremidade esquerda extrema da última linha, terminando com este nó de folha única, que deve ser um nó esquerdo.
Heapcifying significa construir (criar) uma pilha. Como uma árvore onde cada nó pode ter qualquer número de crianças pode ser transformado em uma árvore binária completa, o verdadeiro objetivo deste artigo é produzir a complexidade do tempo para aumentar uma árvore binária completa.
Um exemplo de diagrama de uma árvore binária completa é:
Qualquer nó foliar no nível mais baixo que não tenha um irmão tem que ser um nó esquerdo. Todos os nós da última linha, incluindo um possível nó esquerdo, são "corados" na extremidade esquerda da última linha.
Pela definição de uma pilha, um irmão esquerdo pode ser menor, maior ou igual ao irmão certo. A ordem de ambos os irmãos não é especificada.
Árvore binária completa
A árvore acima é uma árvore binária completa, mas não é uma árvore binária completa. Também é um pó mínimo. Se fosse uma árvore binária completa, todos os nós do último, mas um nível teriam dois filhos cada. A árvore acima é redesenhada abaixo como uma árvore binária completa:
Uma árvore pode ser representada por uma matriz. A árvore é lida de cima para baixo, da esquerda para a direita, linha por linha; então colocado na matriz. A tabela a seguir mostra a variedade de conteúdo e índices para esta árvore:
| 4 | 6 | 12 | 8 | 7 | 16 | 15 | 23 | 10 | 20 | 18 | 25 | nulo | nulo | nulo |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
Os valores celulares estão na primeira tabela linha. Os índices baseados em zero estão na segunda tabela linha.
Relação entre um índice dos pais e seus índices de crianças
Na árvore ou matriz correspondente, a raiz está no índice 0 para indexação baseada em zero. Seja eu a variável para segurar cada índice. Os filhos da raiz estão nos índices 1 e 2, que são 0 + 1 e 0 + 2. Os filhos do nó 1 estão nos índices 3 e 4, que são 1 + 2 e 1 + 3. Os filhos do nó 2 estão no índice 5 e 6, que são 2 + 3 e 2 + 4. Os filhos do nó 3 estão no índice 7 e 8, que são 3 + 4 e 3 + 5. Os filhos do nó 4 estão no índice 9 e 10, que são 4 + 5 e 4 + 6; e assim por diante.
Que eu seja o índice dos pais por enquanto. Portanto, os filhos de cada pai estão no índice i + i + 1 e em i + i + 2, que são:
2i +1 e 2i +2
O inverso deve ser conhecido. Isto é, dado um índice, para um filho esquerdo ou filho direito, qual é o índice dos pais? Para a criança esquerda no índice 1 e a criança certa no índice 2, o pai está no índice 0. Para a criança esquerda no índice 3 e a criança certa no índice 4, o pai está no índice 1. Para a criança esquerda no índice 5 e a criança certa no índice 6, o pai está no índice 2. Para o filho esquerdo no índice 7 e a criança certa no índice 8, o pai está no índice 3. Para a criança esquerda no índice 9 e a criança certa no índice 10, o pai está no índice 4.
I Desta vez, é um índice infantil (não um índice de pais). Portanto, o pai de cada filho esquerdo está no índice I/2 da Divisão Inteiro, e o pai do filho direito, que é o mesmo que o pai do filho esquerdo (irmão), está no resultado inteiro de (i-1) /2, eu.e.:
i/2 e (i-1)/2
onde a divisão é divisão inteira.
Também é bom saber se um nó é um filho esquerdo ou um filho certo: se a divisão normal por 2 tem um restante, esse é um nó esquerdo por indexação baseada em zero. Se a divisão normal por 2 não tiver restante, esse é um nó certo por indexação baseada em zero.
O código em C, para saber se o nó filho é um nó esquerdo ou um nó direito, é:
if (i%2 == 0)
// O nó é um nó direito
outro
// O nó é o nó esquerdo
Depois de saber que um nó é um nó esquerdo, o índice pai pode ser obtido como um resultado inteiro de I/2. Depois de saber que um nó é um nó certo, o índice pai pode ser obtido como um resultado inteiro de (i-1)/2.
Altura de uma pilha binária completa e alguns índices
Número total de nós
Aviso do último diagrama completo acima de que, quando o nível de uma pilha aumenta em 1, seu número total de nós aproximadamente dobra aproximadamente. Precisamente, o próximo nível vem com o número de nós que tornam o novo total, a soma de todos os nós anteriores, mais 1, vezes 2, depois menos 1. Quando a altura é 1, há 1 nó = (0 + 1) x 2 - 1 = 2 - 1 = 21 - 1. Quando a altura é 2, existem 3 nós = (1 + 1) x 2 - 1 = 4 - 1 = 22 - 1. Quando a altura é 3, existem 7 nós = (3 + 1) x 2 - 1 = 8 - 1 = 23 - 1. Quando a altura é 4, existem 15 nós = (7 + 1) x 2 - 1 = 16 - 1 = 24 - 1. Quando a altura é 5, existem 31 nós = (15 + 1) x 2 - 1 = 32 - 1 = 25 - 1. Quando a altura é 6, existem 63 nós = (31 + 1) x 2 - 1 = 64 - 1 = 26 - 1. Quando a altura é 7, existem 127 nós = (63 + 1) x 2 - 1 = 128 - 1 = 27 - 1; e assim por diante.
Em geral, quando a altura é h,
não. de nós = 2h - 1
Índice do último nó
Para uma árvore binária e para indexação baseada em zero, o último índice é:
Último índice = n - 1
onde n é o número total de nós, ou simplesmente o número de nós.
Número de nós sem a última linha
Para uma árvore binária completa, duas vezes o número de nós para a última linha fornece o número total de nós menos 1. Visto de outra maneira, o número de nós para a última fila é igual ao número de todos os nós anteriores, vezes dois, mais 1. Portanto, o número de nós sem a última linha é:
não. de nós sem último = resultado inteiro de n/2
Isso ocorre porque, para indexação baseada em zero, o número total de nós para uma árvore binária completa é sempre um número ímpar. Por exemplo: se o número de nós (total) for 15, então 15/2 = 7½. O resultado inteiro, 7, é levado e a metade é jogada fora. E 7 é o número de nós sem a última linha - veja acima.
Índice para o primeiro nó da última linha
O índice para o primeiro nó da última linha deve ser conhecido. Para indexação baseada em zero, onde o primeiro nó (elemento) está no índice 0, o índice para o primeiro nó da última linha é o número de nós para todos os nós sem a última linha. Isso é:
resultado inteiro de N/2
Observe que na matriz correspondente, os nós da árvore são chamados de elementos.
Peneirar e peneirar
Considere o seguinte sub-árvore de três nós:
Pela propriedade Mínima Heap, o nó pai deve ser menor que ou igual ao menor dos nós das crianças. Portanto, o nó C deve ser trocado pelo mínimo dos nós das crianças; não importa se o menor é o irmão esquerdo ou direito. Isso significa que C deve ser trocado com A para ter:
À medida que “A” se move para tomar o lugar de C, isso está peneirando. À medida que C se move para baixo para tomar o lugar de A, que está peneirando.
Ilustração intensificada
A pilha, como mostrado acima, é uma ordem parcial, do menor valor para o maior valor. Não é uma ordem completa (não classificar). Conforme expresso acima, o heap pode estar em forma de árvore ou em forma de matriz. Como expresso acima, já ocorreu. Na prática, o programador não vai necessariamente encontrar uma árvore já pesada. Ele encontraria uma lista que está completamente em desordem (completamente não classificada). Esta lista desordenada pode existir na forma de uma árvore ou na forma de uma matriz. A seguir, é apresentada uma árvore desordenada (não classificada) e sua matriz correspondente:
A matriz correspondente é:
| 10 | 20 | 25 | 6 | 4 | 12 | 15 | 23 | 8 | 7 | 18 | 16 | nulo | nulo | nulo |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
A árvore é lida em linha a fila, da esquerda para a direita e de cima para baixo, enquanto colocada nas células da matriz. Deixe o nome da matriz ser arr e a variável que representa o índice baseado em zero seja i. Neste artigo, a raiz está no índice 0.
Esta árvore passará por ordem parcial para se tornar uma pilha mínima. Quando a ordem parcial estiver concluída, será a pilha mínima dada na seção de introdução deste artigo. Nesta seção, a ordem parcial é feita manualmente.
Para simplificar o (processo parcial de pedidos parciais), a árvore binária completa não ordenada deve ser feita uma árvore binária completa antes de ser processada. Para torná -lo uma árvore binária completa, adicione elementos cujos valores são maiores que o valor mais alto encontrado já na pilha não ordenada. Neste artigo, isso será feito com a matriz e não com a forma gráfica da árvore.
O elemento mais alto (nó) é 25. Deixe os três números adicionados para fazer uma árvore cheia ser: 26, 27 e 28. A matriz correspondente para a árvore cheia se torna:
| 10 | 20 | 25 | 6 | 4 | 12 | 15 | 23 | 8 | 7 | 18 | 16 | 26 | 27 | 28 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
Quando a lista não ordenada for parcialmente ordenada pela definição de heap, os três últimos elementos permanecerão em suas últimas posições; e pode ser facilmente abandonado.
Quando esta lista não ordenada é parcialmente ordenada pela definição de heap, seria a lista parcialmente ordenada fornecida acima (introdução). Uma lista parcialmente ordenada tem alguma classificação, mas não é uma ordem completa (não é uma classificação completa).
Rearranjo manual (edifício da pilha)
A matriz não ordenada pode ser colocada assim:
10 20 25 06 04 12 15 23 08 07 18 16 26 27 28
Existem 15 elementos. O resultado inteiro de 15/2 é 7. A lista deve ser dividida em duas metades, com o primeiro tempo sendo 7 e o segundo tempo, 8, como segue:
10 20 25 06 04 12 15 | 23 08 07 18 16 26 27 28
Esta divisão pode ser considerada como uma operação principal. A construção de heap continua da extremidade direita com os pares de elementos, 27 e 28, identificados como filhos de 15. 15 é menor que 27 ou 28. Portanto, este sub-árvore de três nós satisfaz a propriedade Minimum Heap, e os nós não são tocados por agora. Esta verificação pode ser considerada outra operação principal. Portanto, existem duas operações principais até agora (uma divisão de matriz e uma verificação).
16 e 26 são crianças de 12. 12 é menor que 16 ou 26. Portanto, este sub-árvore de três nós satisfaz a propriedade Minimum Heap, e os nós não são tocados (por enquanto). Esta verificação pode ser considerada outra operação principal. Portanto, existem três operações principais até agora (uma divisão e dois cheques).
07 e 18 são os filhos de 04. 04 é menor que 07 ou 18. Portanto, este sub-árvore de três nós satisfaz a propriedade Minimum Heap, e os nós não são tocados (por enquanto). Esta verificação pode ser considerada outra operação principal. Portanto, existem quatro operações principais até agora (uma divisão e três cheques).
23 e 08 são os filhos de 06. 06 é menor que 23 ou 08. Portanto, este sub-árvore de três nós satisfaz a propriedade Minimum Heap, e os nós não são tocados (por enquanto). Esta verificação pode ser considerada outra operação principal. Portanto, existem cinco operações principais até agora (uma divisão e quatro cheques).
Todos os 8 elementos da última fila da árvore e seus pais foram verificados. Para ir para o nível anterior, a parte esquerda da árvore deve ser dividida por 2, e o resultado inteiro é tomado. O resultado inteiro de 7/2 é 3. A nova colocação da lista é:
10 20 25 | 06 04 12 15 | 23 08 07 18 16 26 27 28
Esta divisão pode ser considerada como uma operação principal. Portanto, existem seis operações principais até agora (duas divisões e quatro cheques).
12 e 15 são filhos de 25. 25 é maior que 12 ou 15. Este sub-árvore de três nós não satisfaz a propriedade Minimum Heap, então os nós devem ser tocados. No entanto, essa verificação ainda pode ser considerada outra operação principal. Portanto, existem sete operações principais até agora (duas divisões e cinco cheques).
Tibportar para baixo tem que ocorrer e possivelmente até a última fila. Cada peneiração (troca) é a operação principal.
25 é trocado pelo menor de seus filhos, 12 para dar a configuração:
10 20 12 | 06 04 25 15 | 23 08 07 18 16 26 27 28
25 está agora no terceiro nível e não está mais no segundo nível. 25 agora é o pai de 16 e 26. Neste ponto, 25 passa a ser superior a 16, mas menor que 26. Então 25 e 16 são trocados. Essa troca é outra operação principal e, portanto, existem nove operações principais (duas divisões, cinco cheques e dois swaps). A nova configuração é:
10 20 12 | 06 04 16 15 | 23 08 07 18 25 26 27 28
No segundo nível da lista dada, havia 20 e 25. 25 foi peneirado até a última fila. 20 ainda está para ser verificado.
Atualmente, 06 e 04 são crianças de 20. 20 é maior que 06 ou 04. Este sub-árvore de três nós não satisfaz a propriedade Minimum Heap, então os nós devem ser tocados. No entanto, essa verificação ainda pode ser considerada outra operação principal. Portanto, existem dez operações principais até agora (duas divisões, seis cheques e duas swaps). Tibportar para baixo tem que ocorrer e possivelmente até a última fila. Cada peneiração (troca) é a operação principal.
20 é trocado pelo mínimo de seus filhos, 04 para dar a configuração:
10 04 12 | 06 20 16 15 | 23 08 07 18 25 26 27 28
20 está agora no terceiro nível e não está mais no segundo nível. 20 agora é o pai de 07 e 18. Neste ponto, 20 é maior que 07 ou 18. Então 20 e 07 são trocados. Essa troca é outra operação principal e, portanto, existem doze operações principais até agora (duas divisões, seis cheques e quatro swaps). A nova configuração é:
10 04 12 | 06 07 16 15 | 23 08 20 18 25 26 27 28
Tirradores para baixo do caminho anterior terminaram. A parte esquerda que não foi completamente verificada deve ser dividida em dois (indo para o nível anterior) para ter:
10 | 04 12 | 06 07 16 15 | 23 08 20 18 25 26 27 28
O resultado inteiro de 3/2 é 1.
Atualmente, 04 e 12 são filhos de 10. 10 é maior que 04, mas menor que 12. Este sub-árvore de três nós não satisfaz a propriedade Minimum Heap, então os nós devem ser tocados. No entanto, essa verificação ainda deve ser considerada como outra operação principal. Portanto, existem quatorze operações principais até agora (três divisões, sete cheques e quatro swaps). Tibportar para baixo tem que ocorrer e possivelmente até a última fila. Cada peneiração (troca) é a operação principal.
10 é trocado pelo mínimo de seus filhos, 04 para dar a configuração:
04 | 10 12 | 06 07 16 15 | 23 08 20 18 25 26 27 28
10 está agora no segundo nível e não está mais no primeiro nível. 10 agora é o pai 06 e 07. Neste ponto, 10 é maior que 06 ou 07. Então 10 e 06 são trocados. Essa troca é outra operação principal e, portanto, existem dezesseis operações principais até agora (três divisões, sete cheques e seis swaps). A nova configuração é:
04 | 06 12 | 10 07 16 15 | 23 08 20 18 25 26 27 28
10 está agora no terceiro nível e não está mais no segundo nível. 10 agora é o pai 23 e 08. Neste ponto, 10 é menor que 23, mas maior que 08. Então 10 e 08 são trocados. Essa troca é outra operação principal e, portanto, há dezessete operações principais até agora (três divisões, sete cheques e sete swaps). A nova configuração é:
04 | 06 12 | 08 07 16 15 | 23 10 20 18 25 26 27 28
Bem, a verificação, a divisão e a troca começou no último índice e atingiu o primeiro índice, com todas as consequências de peneiradas descendentes. Isso significa que a construção de heap está completa e, neste caso, com dezessete operações principais (três divisões, sete cheques e sete swaps). Havia 15 elementos, embora os três últimos fossem os elementos fictícios necessários para simplificar a construção de heap.
Algoritmo
Existem diferentes algoritmos para construção de heap. A ilustração dada acima será a mais eficiente se o valor dos pais for trocado por qualquer uma das crianças que são menores e nem sempre as menores dos filhos. As etapas para o algoritmo são:
- Divida todo o número de elementos por dois.
- Continue da metade direita, verificando um par de irmãos com os pais e trocando se necessário.
- Quando todos os nós do último nível forem verificados, com possível troca, prossiga para o nível anterior e repita as duas etapas acima. A troca está penetrando, e isso pode ter que atingir o nível mais baixo.
- Quando a raiz for verificada e possivelmente trocada, pare.
Complexidade do tempo
A complexidade do tempo é o tempo de execução relativo de algum código. Nesse caso, é o tempo de execução relativo do processo de construção de heap. A complexidade do tempo é na verdade o número de operações principais no código (programa).
Oficialmente, diz -se que a complexidade do tempo do algoritmo para este artigo é n operações, onde n é o número de elementos na matriz não ordenada mais os elementos fictícios. Nesse caso, n é 15. Portanto, a complexidade do tempo para este algoritmo é 15.
Por que deveria ser 15 em vez de 17? Isto é, por que deveria ser n? - Bem, como a divisão não é partição, a duração de cada ação de divisão é pequena e pode ser negligenciada. Com isso e para a ilustração acima, o número de operações principais se tornará 14 (sete cheques e sete swaps), com as 3 divisões ignoradas.
Além disso, se o valor dos pais for trocado por qualquer uma das crianças que são menores, e nem sempre as menores dos filhos, o tempo geral de verificação será reduzido. Isso tornará o tempo de verificação pequeno e tão ignorado. Com isso e para a ilustração acima, o número de operações principais se tornará 7 (sete swaps), com as 3 divisões ignoradas e os sete cheques também ignorados.
NOTA: Para um bom programa de construção de heap, apenas as operações de troca (peneirar baixos neste caso) são consideradas na complexidade do tempo. Nesse caso, existem 7 operações e não 15. Ao lidar com a complexidade do tempo, o número máximo possível de operações é o que deve ser dado.
É possível que todos os 15 nós acima sejam trocados. Portanto, a complexidade do tempo para este exemplo deve ser dada como 15 e não 7.
A complexidade do tempo para este algoritmo é dada, em termos gerais, como:
Sobre)
onde n é n, esta é a notação grande. Esta notação usa maiúsculas o e seus parênteses. Dentro dos parênteses está a expressão para o possível número máximo de operações para o código (programa) para concluir.
Codificação em c
A função principal C para intensificar a matriz acima mencionada é:
int main (int argc, char ** argv)
int n1 = 12;
int a1 [] = 10, 20, 25, 6, 4, 12, 15, 23, 8, 7, 18, 16;
int a2 [] = 10, 20, 25, 6, 4, 12, 15, 23, 8, 7, 18, 16, 26, 27, 28;
BuildHeap (A2, N2);
para (int i = 0; i = arr [leftindx] && arr [leftindx]> = arr [redestindx])
int temp = arr [parentindx]; arr [parentindx] = arr [rightindx]; arr [RightIndx] = temp;
lastDown = RETERTINDX;
caso contrário, if (arr [parentindx]> = arr [rightindx] && arr [rightindx]> = arr [leftindx])
int temp = arr [parentindx]; arr [parentindx] = arr [leftindx]; arr [leftindx] = temp;
lastdown = leftindx;
caso contrário, if (arr [parentindx]> = arr [rightindx] && arr [rightindx] = arr [leftindx] && arr [leftindx] <= arr[rightIndx])
int temp = arr [parentindx]; arr [parentindx] = arr [leftindx]; arr [leftindx] = temp;
lastdown = leftindx;
retornar lastdown;
Existe uma função de peneirar. Ele usaria a função swap () e peneiraria direto para o nível mais baixo em um caminho. Isso é:
int nextindx;
Void Siftdown (int arr [], int n2, int i)
int leftindx, RightIndx;
int parentindx = i;
leftindx = 2*i+1;
rightindx = 2*i+2;
if (parentindx = 0)
nextIndx = swap (arr, parentindx, leftindx, rightindx);
if (nextindx = halfindx/2; i--)
Siftdown (A2, N2, I);
N = n/2;
if (n> = 1)
BuildHeap (A2, N);
Todos os segmentos de código acima podem ser montados para formar um programa que irá alimentar a matriz não ordenada.
Conclusão
O algoritmo mais eficiente para a complexidade do tempo Heapify é:
Sobre)