Heaps e Filas de Prioridade

Um min-heap binário é uma árvore binária completa que satisfaz:

key(parent) <= key(child)

O fato de ser completa permite uma representação compacta em array. Para um índice i baseado em zero:

• pai: (i - 1) / 2 para i > 0;
• filho esquerdo: 2i + 1;
• filho direito: 2i + 2.

Operações

Operação	Heap binário
Consultar o mínimo	Θ(1)
Inserir	O(log n)
Remover o mínimo	O(log n)
Construir com n itens	Θ(n)
Encontrar um valor arbitrário	Θ(n)

A construção bottom-up é linear porque a maioria dos nós está perto das folhas e percorre apenas uma distância curta. Multiplicar n nós por log n fornece um limite superior válido, mas pouco justo.

Java

Queue<Integer> priorities = new PriorityQueue<>();
priorities.add(8);
priorities.add(3);
priorities.add(5);
int smallest = priorities.remove(); // 3

Não há garantia de que a iteração sobre um PriorityQueue produza uma ordem classificada; apenas as operações sobre a cabeça seguem o contrato de prioridade.

Exercícios

1. Restaure o heap após remover a raiz.
2. Derive um comparador para max-heap sem overflow na subtração de inteiros.
3. Explique por que um heap não é uma estrutura eficiente de busca geral.