- Aplicando o buildheap no array
consegue-se transforma-lo em uma max-heap. Depois disso realiza-se as operações: extractRoot(), insert(14), extractRoot(), extractRoot(). Qual seria o estado final da heap após essas operações?
Passo 1
O enunciado dá um array inicial
e pede para, primeiro, transformar esse array numa max‐heap usando o algoritmo buildheap (bottom‐up). Depois, sobre essa heap, executar em sequência:
e pede para, primeiro, transformar esse array numa max‐heap usando o algoritmo buildheap (bottom‐up). Depois, sobre essa heap, executar em sequência:
Vamos precisar entender como o buildheap reorganiza o array em tempo linear (fazendo heapify de cada subárvore) e como funcionam as operações de remoção da raiz (troca com o último elemento, diminui o tamanho e faz heapify no topo) e de inserção (coloca na última posição e faz “bubble-up”).
Passo 2
Aplicando buildheap em
(índice de 1 a 9), começa-se em
e desce fazendo heapify. O resultado final é a max‐heap
Passo 3
Fazendo o primeiro
:
- Remove-se
da raiz e coloca-se na raiz o último elemento . - Diminui-se o tamanho para 8 e faz‐se heapify em 1:
Passo 4
Executa-se
:
- Coloca-se
na nova posição 9:
. - Faz‐se “bubble-up”:
Passo 5
Fazendo o segundo
:
- Remove-se
e introduz-se na raiz o último , tamanho vai a 8:
. - Heapify em 7:
Passo 6
Fazendo o terceiro
:
- Remove-se
e coloca-se na raiz o último , tamanho vai a 7:
. - Heapify em 3:
Resposta
O estado final da heap é