Síntese: qual padrão usar?
Três padrões de heap cobertos. A seção é curta, mas o reflexo que ela treina é poderoso: reconhecer quando a pergunta é sobre extremos repetidos e sacar o heap.
A árvore de decisão da seção
O problema pede o MENOR ou o MAIOR repetidamente, sem precisar de tudo ordenado?
→ pense em HEAP. Daí:
1. "Os K maiores / menores / K-ésimo / K mais frequentes"?
→ HEAP DE TAMANHO K (K maiores → min-heap; K menores → max-heap)
2. "Fundir / pegar o próximo menor entre VÁRIAS fontes ordenadas"?
→ K-WAY MERGE (min-heap com a cabeça de cada fonte)
3. "Mediana de um fluxo / equilibrar duas metades"?
→ DOIS HEAPS (max-heap da metade menor + min-heap da maior)
E o reflexo geral: heap = "qual o extremo agora?" em O(log n). Se você se pegar querendo reordenar a cada passo, ou comparar repetidamente para achar o mínimo/máximo de um conjunto que muda, é sinal de heap.
O mapa completo da seção
| Padrão | Pergunta-chave | Estrutura | Tempo |
|---|---|---|---|
| Top-K | "os K maiores/menores" | heap de tamanho K | O(n log k) |
| k-way merge | "próximo menor entre K fontes" | min-heap de K cabeças | O(N log k) |
| Dois heaps | "mediana de um fluxo" | max-heap + min-heap | O(log n)/inserção |
A ideia que une tudo: o heap mantém o extremo acessível em O(1) e se reajusta em O(log n) quando o conjunto muda. Por isso ele é a ferramenta de "prioridade" — e reaparece como fila de prioridade no Dijkstra (grafos) e em agendadores.
Quiz da seção
Enunciados que você não viu nas aulas. Identifique o padrão e o porquê. 6+ acertos: pronto para a prova.
🧠 Quiz da seção: Heap
0/61. 'Retorne os K pontos mais próximos da origem.' Qual padrão e qual heap?
2. 'Conecte todos os bastões com custo mínimo (juntar a e b custa a+b).' Qual padrão?
3. 'Fluxo de números; a qualquer momento, retorne a mediana atual.' Qual padrão?
4. 'Funda K arrays ordenados num só.' Por que o heap bate concatenar+ordenar?
5. Para os K MAIORES elementos, qual tipo de heap de tamanho K e por quê?
6. Qual a ideia-mãe que define quando usar um heap?
Pronto para a prova?
A prova final da seção Heap tem três problemas inéditos — fácil, médio e difícil — com casos ocultos. O difícil (k-ésimo menor numa matriz ordenada) é um k-way merge disfarçado: comece pelo canto e expanda vizinhos com um min-heap. As três aulas cobrem tudo que você precisa.
Boa prova! Volte para a página da seção e clique em "Prova final".