(Questão 04-03 pontos)

Mostre, passo a passo, como obter o heap de prioridade máxima resultante do vetor abaixo.
4 1 7 7 2 16 9 11 14 18 71

Passo 1

O enunciado dá o vetor de 11 elementos
[4,;1,;7,;7,;2,;16,;9,;11,;14,;18,;71]
e pede o heap de prioridade máxima resultante. O conteúdo aqui é a construção de um max-heap a partir de um array usando o algoritmo Build-Max-Heap. Vamos usar indexação 1··· 11, definir n=11 e aplicar MAX-HEAPIFY em cada nó i de lfloor n/2rfloor até 1.

Passo 2

Começamos em i=lfloor11/2rfloor=5.
Elemento em 5: 2. Seus filhos são em 10: 18 e em 11: 71. O maior filho é 71 em 11.
Troca 2rightarrow71 e não há mais filhos para o novo 2.
Novo array:
[4,;1,;7,;7,;71,;16,;9,;11,;14,;18,;2]

Passo 3

Agora i=4.
Elemento em 4: 7. Filhos: em 8: 11, em 9: 14. Maior é 14 em 9.
Troca 7rightarrow14. O 7 em 9 não tem filhos.
Novo array:
[4,;1,;7,;14,;71,;16,;9,;11,;7,;18,;2]

Passo 4

Agora i=3.
Elemento em 3: 7. Filhos: em 6: 16, em 7: 9. Maior é 16 em 6.
Troca 7rightarrow16. O 7 em 6 não tem filhos.
Novo array:
[4,;1,;16,;14,;71,;7,;9,;11,;7,;18,;2]

Passo 5

Agora i=2.
Elemento em 2: 1. Filhos: em 4: 14, em 5: 71. Maior é 71 em 5.
Troca 1rightarrow71, obtendo
[4,;71,;16,;14,;1,;7,;9,;11,;7,;18,;2]
No novo nó 5 (valor 1), filhos em 10: 18, em 11: 2. Maior é 18 em 10.
Troca 1rightarrow18.
Novo array:
[4,;71,;16,;14,;18,;7,;9,;11,;7,;1,;2]

Passo 6

Finalmente i=1.
Elemento em 1: 4. Filhos: em 2: 71, em 3: 16. Maior é 71 em 2.
Troca 4rightarrow71, obtendo
[71,;4,;16,;14,;18,;7,;9,;11,;7,;1,;2]
No novo nó 2 (valor 4), filhos em 4: 14, em 5: 18. Maior é 18 em 5.
Troca 4rightarrow18, obtendo
[71,;18,;16,;14,;4,;7,;9,;11,;7,;1,;2]
O novo 4 em 5 tem filhos em 10: 1 e 11: 2, ambos menores, logo encerramos.

Resposta

O max-heap resultante (array 1··· 11) é
[71,;18,;16,;14,;4,;7,;9,;11,;7,;1,;2]

Exercícios relacionados