- Insira os elementos
nessa ordem em uma min heap vazia e mostre seu estado final
Passo 1
O enunciado pede para inserir, em uma min‐heap inicialmente vazia, os elementos na ordem
e apresentar o estado final da heap. O conteúdo é “heap mínimo” (min‐heap) e o procedimento que vamos usar é o de inserção com “percolate‐up” (sobe‐para‐cima) para manter a propriedade de heap: cada nó pai deve ser menor ou igual a seus filhos.
e apresentar o estado final da heap. O conteúdo é “heap mínimo” (min‐heap) e o procedimento que vamos usar é o de inserção com “percolate‐up” (sobe‐para‐cima) para manter a propriedade de heap: cada nó pai deve ser menor ou igual a seus filhos.
Passo 2
Algoritmo de inserção em min‐heap (implementação típica em vetor 1-indexado):
- Coloca o novo elemento no fim do vetor (o último “nó” livre na árvore completa).
- Enquanto esse nó não for a raiz (índice
) e seu valor for menor que o do pai (índice ), troca o nó com o pai e atualiza .
Esse procedimento garante que a propriedade de min‐heap seja restaurada a cada inserção.
Passo 3
Como estamos inserindo os elementos em ordem crescente, cada novo valor é sempre maior que todos os já presentes na heap. Logo, ao inserir cada elemento não ocorre nenhuma troca no passo de “percolate‐up” (o nó novo já fica na posição correta).
Passo 4
Portanto, após inserir sucessivamente
sem nenhuma troca, o vetor que representa a min‐heap em ordem de nível (array 1-indexado) fica simplesmente:
Em forma de árvore completa, o resultado é
1
/ \
/ \
/ \ / \
/ \ /
Resposta
O array‐representação da min‐heap final é