1. A sequência [23,17,14,6,13,10,1,5,7,12] é uma heap? Justifique sua resposta

Passo 1

O enunciado dá a sequência de chaves \r \,[23,17,14,6,13,10,1,5,7,12]
\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 i tem filhos nas posições 2i e 2i+1, se existirem.

Passo 2

Definição de max-heap em vetor A de tamanho n: \r
para todo i tal que 1\le i\le \lfloor n/2\rfloor devemos ter \r
A[i]\;\ge\;A[2i]\quad\text{e}\quad A[i]\;\ge\;A[2i+1]\r
sempre que os índices do filho não ultrapassem n.

Passo 3

Numerando o vetor de 1 a 10, temos \r
\begin{aligned}\r A[1]&=23,&A[2]&=17,&A[3]&=14,\\\ A[4]&=6, &A[5]&=13,&A[6]&=10,\\\ A[7]&=1, &A[8]&=5,&A[9]&=7, &A[10]&=12.\r \end{aligned} \r
Os pares pai→filho são: \r
1\to(2,3), 2\to(4,5), 3\to(6,7), 4\to(8,9), 5\to(10).

Passo 4

Verificamos as desigualdades: \r
  • A[1]=23\ge17=A[2] e 23\ge14=A[3]. \r
  • A[2]=17\ge6=A[4] e 17\ge13=A[5]. \r
  • A[3]=14\ge10=A[6] e 14\ge1=A[7]. \r
  • A[4]=6\ge5=A[8] mas 6<7=A[9], 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 A[4]=6<7=A[9], contrariando a condição de que cada pai deve ser ≥ de seus filhos.

Exercícios relacionados