- A sequência
é uma heap? Justifique sua resposta
Passo 1
O enunciado dá a sequência de chaves \r
\r
e pergunta se isso forma um max-heap (estrut. de dados completa onde cada nó-pai tem valor ≥ de seus filhos). \r
Para responder, vamos usar a representação em vetor, em que o nó na posição tem filhos nas posições
e
, se existirem.
\r
e pergunta se isso forma um max-heap (estrut. de dados completa onde cada nó-pai tem valor ≥ de seus filhos). \r
Para responder, vamos usar a representação em vetor, em que o nó na posição
Passo 2
Definição de max-heap em vetor
de tamanho
: \r
para todo tal que
devemos ter \r
para todo
sempre que os índices do filho não ultrapassem
.
Passo 3
Numerando o vetor de 1 a 10, temos \r
\r
Os pares pai→filho são: \r
(2,3),
(4,5),
(6,7),
(8,9),
(10).
Passo 4
Verificamos as desigualdades: \r
-
e . \r -
e . \r -
e . \r -
mas , ou seja, o filho em posição 9 é maior que o pai em posição 4, violando a propriedade de max-heap.
Resposta
Não é heap, pois
, contrariando a condição de que cada pai deve ser ≥ de seus filhos.