1. Aplicando o buildheap no array [1,3,5,7,9,11,13,15,17] 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 [1,3,5,7,9,11,13,15,17]
e pede para, primeiro, transformar esse array numa max‐heap usando o algoritmo buildheap (bottom‐up). Depois, sobre essa heap, executar em sequência:
  1. \mathrm{extractRoot}()
  2. \mathrm{insert}(14)
  3. \mathrm{extractRoot}()
  4. \mathrm{extractRoot}()
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 [1,3,5,7,9,11,13,15,17] (índice de 1 a 9), começa-se em \lfloor 9/2\rfloor=4 e desce fazendo heapify. O resultado final é a max‐heap
[17,15,13,7,9,11,5,3,1].

Passo 3

Fazendo o primeiro \mathrm{extractRoot}():
  • Remove-se 17 da raiz e coloca-se na raiz o último elemento 1.
  • Diminui-se o tamanho para 8 e faz‐se heapify em 1:
[1,15,13,7,9,11,5,3] \;\longrightarrow\; [15,1,13,7,9,11,5,3] \;\longrightarrow\; [15,9,13,7,1,11,5,3].

Passo 4

Executa-se \mathrm{insert}(14):
  • Coloca-se 14 na nova posição 9:
    [15,9,13,7,1,11,5,3,14].
  • Faz‐se “bubble-up”:
14>7\;(índice\\\ 4)\;\longrightarrow\;[15,9,13,14,1,11,5,3,7] \;\longrightarrow\; 14>9\;(índice\\\ 2)\;\longrightarrow\;[15,14,13,9,1,11,5,3,7].íí

Passo 5

Fazendo o segundo \mathrm{extractRoot}():
  • Remove-se 15 e introduz-se na raiz o último 7, tamanho vai a 8:
    [7,14,13,9,1,11,5,3].
  • Heapify em 7:
[7,14,13,9,1,11,5,3] \;\longrightarrow\; [14,7,13,9,1,11,5,3] \;\longrightarrow\; [14,9,13,7,1,11,5,3].

Passo 6

Fazendo o terceiro \mathrm{extractRoot}():
  • Remove-se 14 e coloca-se na raiz o último 3, tamanho vai a 7:
    [3,9,13,7,1,11,5].
  • Heapify em 3:
[3,9,13,7,1,11,5] \;\longrightarrow\; [13,9,3,7,1,11,5] \;\longrightarrow\; [13,9,11,7,1,3,5].

Resposta

O estado final da heap é
[13,9,11,7,1,3,5].

Exercícios relacionados