1. Insira os elementos [1,2,3,4,5,6,7,8,9,10] nessa ordem em uma max heap vazia e mostre seu estado final

Passo 1

O enunciado pede para inserir, em ordem, os elementos [1,2,3,4,5,6,7,8,9,10] em uma max‐heap inicialmente vazia e, ao final, mostrar como fica essa heap representada em vetor. O conteúdo envolvido é a estrutura de dados heap e o procedimento de inserção com “bubble‐up” (ou “sift‐up”) para restaurar a propriedade de max‐heap.

Passo 2

O algoritmo de inserção em uma max‐heap representada por vetor funciona assim:
  1. Coloca o novo elemento no fim do vetor.
  2. Enquanto ele não estiver na raiz (índice 1) e for maior que seu pai, troca‐se com o pai.
  • Se o novo elemento ficou na posição i, seu pai está em \lfloor i/2\rfloor.
  • A cada troca, atualiza-se i\leftarrow\lfloor i/2\rfloor e repete até restaurar a propriedade de max-heap (pai ≥ filhos).

Passo 3

Aplicando esse procedimento para inserir, em sequência, \;1,2,\dots,10\; em uma max‐heap vazia, ao final obtemos a seguinte representação em vetor (índices de 1 a 10):
[10,\,9,\,6,\,7,\,8,\,2,\,5,\,1,\,4,\,3].

Resposta

[10,\,9,\,6,\,7,\,8,\,2,\,5,\,1,\,4,\,3]

Exercícios relacionados