1. Considere uma min-heap inicialmente vazia onde os elementos são inseridos nela de forma a deixá-la com o último nível completo. O preenchimento se dá em um laço, cuja quantidade de iterações é determinada de forma automática, baseado no nível/altura da heap. Por exemplo, uma heap de altura 0 , seria preenchida com os elementos de [1]. Uma heap de altura 1 seria preenchida com os elementos [3,2,1], uma heap com altura 2 seria preenchida com os elementos [7, \ldots, 1] e assim por diante.
    a. Encontre o array necessário para preencher uma heap com altura h (em função de h )
    b. Encontre o número de trocas que acontecem com os elementos que são inseridos em um determinado nível h da heap (número de trocas em função de h, onde h é um determinado nível da heap)

Passo 1

O enunciado quer usar inserções sequenciais numa min-heap vazia, de modo a deixá-la completa até a altura h. Cada inserção faz “bubble-up” (trocas com o pai) até restaurar a propriedade de heap. Precisamos determinar:
a) o array de valores a inserir (em função de h);
b) o total de trocas que ocorrem ao inserir todos os nós do nível h.

Passo 2

Uma árvore binária completa de altura h tem
N \;=\;\sum_{i=0}^{h}2^i \;=\;2^{h+1}-1
nós.

Passo 3

Para forçar que cada nova inserção seja sempre o menor valor até então (e assim conte todas as trocas possíveis), usamos como valores exatamente os inteiros de 1 a N em ordem decrescente. Logo, o array de inserção é
\bigl[\,N,\;N-1,\;\dots,\;2,\;1\,\bigr]
com N=2^{h+1}-1.

Passo 4

Quando inserimos o k-ésimo valor e ele cai na primeira posição livre do nível d, em heap por inserção ele faz até d trocas (uma para cada degrau até a raiz). No nosso caso, cada valor que vai para o nível h é menor que todos os anteriores, então ele “borbulha” exatamente h vezes.

Passo 5

No nível h 2^h posições. Cada uma delas, na inserção, provoca h trocas. Portanto o total de trocas para o nível h é
2^h \times h.

Resposta

a) O array de inserção para altura h é
\bigl[\,2^{h+1}-1,\;2^{h+1}-2,\;\dots,\;1\,\bigr].
b) O número total de trocas ao inserir todos os nós do nível h é
2^h \,h.

Exercícios relacionados