- 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
, uma heap com altura 2 seria preenchida com os elementos
e assim por diante.
a. Encontre o array necessário para preencher uma heap com altura
(em função de
)
b. Encontre o número de trocas que acontecem com os elementos que são inseridos em um determinado nível
da heap (número de trocas em função de
, onde
é um determinado nível da heap)
a. Encontre o array necessário para preencher uma heap com altura
b. Encontre o número de trocas que acontecem com os elementos que são inseridos em um determinado nível
Passo 1
O enunciado quer usar inserções sequenciais numa min-heap vazia, de modo a deixá-la completa até a altura
. 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 );
b) o total de trocas que ocorrem ao inserir todos os nós do nível .
a) o array de valores a inserir (em função de
b) o total de trocas que ocorrem ao inserir todos os nós do nível
Passo 2
Uma árvore binária completa de altura
tem
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
a
em ordem decrescente. Logo, o array de inserção é
com
.
Passo 4
Quando inserimos o
-ésimo valor e ele cai na primeira posição livre do nível
, em heap por inserção ele faz até
trocas (uma para cada degrau até a raiz). No nosso caso, cada valor que vai para o nível
é menor que todos os anteriores, então ele “borbulha” exatamente
vezes.
Passo 5
No nível
há
posições. Cada uma delas, na inserção, provoca
trocas. Portanto o total de trocas para o nível
é
Resposta
a) O array de inserção para altura
é
b) O número total de trocas ao inserir todos os nós do nível
é