Quais das seguintes árvores representa um heap?

Alternativa B

Para identificar qual estrutura representa um Heap, precisamos verificar duas propriedades fundamentais:

1. Propriedade de Heap (Ordem): Em um Max-Heap, cada nó pai deve ser maior ou igual aos seus filhos (Pai \geq Filhos). Em um Min-Heap, cada pai deve ser menor ou igual (Pai \leq Filhos).
2. Propriedade de Completude: O Heap deve ser uma Árvore Binária Completa. Isso significa que todos os níveis devem estar totalmente preenchidos, exceto possivelmente o último, que deve ser preenchido da esquerda para a direita, sem "buracos".

Análise das Árvores

Árvore I

• Estrutura: Raiz 2, filhos 6 (esquerda) e 1 (direita).
• Verificação:
• Para Max-Heap: $2 \geq 6$ é falso.
• Para Min-Heap: $2 \leq 6$ é verdadeiro, mas $2 \leq 1$ é falso.
• Conclusão: Não satisfaz a propriedade de ordem. Não é um heap.

Árvore II

• Estrutura:
• Nível 0: 8
• Nível 1: 6 (esq), 4 (dir)
• Nível 2: 3 (filho de 6), 2 (filho de 4)
• Verificação:
• Ordem (Max-Heap):
• $8 \geq 6$ e $8 \geq 4$ (OK)
• $6 \geq 3$ (OK)
• $4 \geq 2$ (OK)
• Completude: Os nós estão preenchidos sequencialmente da esquerda para a direita. Não há buracos.
• Conclusão: É um Max-Heap válido.

Árvore III

• Estrutura: Raiz 9, nó 5.
• Verificação:
• Ordem: $9 \geq 5$ (Satisfaz Max-Heap).
• Completude: Esta é a chave da questão. Embora o nó 5 esteja visualmente deslocado, a linha de conexão sai do lado direito inferior do nó 9, indicando que ele é um filho direito.
• Em uma Árvore Binária Completa, é obrigatório preencher o filho esquerdo antes do filho direito. Como não há um nó à esquerda do 9, a árvore possui um "buraco" no nível 1 (índice esquerdo vazio).
• Conclusão: Viola a propriedade de completude. Não é um heap.

Conclusão

Apenas a árvore II satisfaz simultaneamente a propriedade de ordem (Max-Heap) e a propriedade de completude estrutural exigida para Heaps Binários.

Portanto, a alternativa correta é a b.