(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
4 1 7 7 2 16 9 11 14 18 71
Passo 1
O enunciado dá o vetor de
elementos
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
···
, definir
e aplicar MAX-HEAPIFY em cada nó
de
até
.
Passo 2
Começamos em
.
Elemento em :
. Seus filhos são em
:
e em
:
. O maior filho é
em
.
Troca e não há mais filhos para o novo
.
Novo array:
Elemento em
Troca
Novo array:
Passo 3
Agora
.
Elemento em :
. Filhos: em
:
, em
:
. Maior é
em
.
Troca . O
em
não tem filhos.
Novo array:
Elemento em
Troca
Novo array:
Passo 4
Agora
.
Elemento em :
. Filhos: em
:
, em
:
. Maior é
em
.
Troca . O
em
não tem filhos.
Novo array:
Elemento em
Troca
Novo array:
Passo 5
Agora
.
Elemento em :
. Filhos: em
:
, em
:
. Maior é
em
.
Troca , obtendo
Elemento em
Troca
No novo nó
(valor
), filhos em
:
, em
:
. Maior é
em
.
Troca .
Novo array:
Troca
Novo array:
Passo 6
Finalmente
.
Elemento em :
. Filhos: em
:
, em
:
. Maior é
em
.
Troca , obtendo
Elemento em
Troca
No novo nó
(valor
), filhos em
:
, em
:
. Maior é
em
.
Troca , obtendo
Troca
O novo
em
tem filhos em
:
e
:
, ambos menores, logo encerramos.
Resposta
O max-heap resultante (array
···
) é