Padrão 1: Top-K com heap de tamanho K
"Os K maiores", "o K-ésimo menor", "os K mais frequentes" — uma família inteira de problemas. A sacada: você não precisa ordenar tudo. Basta um heap que guarda só os K melhores vistos até agora.
Tente primeiro: Kth Largest Element in an Array
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Retorne o k-ésimo MAIOR elemento de nums (o k-ésimo na ordem decrescente, contando repetições).
Exemplo: nums = [3,2,1,5,6,4], k = 2 → 5.
(Em Python há heapq; em JS, a solução inclui uma pequena classe de heap, já que a linguagem não tem uma nativa.)
Tentou? Ordenar o array e pegar a posição certa funciona (O(n log n)) — e passa! Mas há uma abordagem que é melhor quando K é pequeno e o fluxo é grande. A teoria abaixo mostra o heap de tamanho K.
A teoria: um heap de tamanho fixo K
Para achar o K-ésimo maior, mantenha um min-heap com no máximo K elementos — os K maiores vistos até agora. O truque é contraintuitivo: para guardar os maiores, use um min-heap, porque assim o menor dos K grandes fica no topo, fácil de descartar:
para cada número x:
empurre x no heap
se o heap passou de K elementos:
remova o topo (o menor) → sobram os K maiores
no fim: o topo do heap é o K-ésimo maior
Por que funciona? O heap sempre contém os K maiores até agora; seu menor elemento (o topo) é exatamente o K-ésimo maior. Qualquer número menor que esse topo é descartado na hora.
Por que O(n log k) — e quando vale a pena?
São n elementos; cada push/pop custa O(log k) (o heap nunca passa de K).
Total: O(n log k), com O(k) de espaço. Compare com ordenar tudo
(O(n log n), O(n) de espaço): quando k é bem menor que n, log k ≪ log n, e
o heap ganha — além de funcionar para fluxos (dados que chegam aos poucos),
onde ordenar tudo nem seria possível.
| Abordagem | Tempo | Espaço | Boa quando |
|---|---|---|---|
| Ordenar tudo | O(n log n) | O(n) | precisa de tudo ordenado |
| Heap de tamanho K | O(n log k) | O(k) | K ≪ n, ou fluxo |
Exemplo: Top K Frequent Elements
"Os K elementos que mais aparecem." Combina dois padrões que você já tem:
contagem de frequência (hash map, da seção Array/String) + top-K com
heap. Conte as frequências, depois use um heap de tamanho K sobre os pares
(frequência, elemento):
A lição: para os K maiores, use um MIN-heap
A inversão é a parte que confunde — e por isso vale fixar: K maiores → min-heap de tamanho K (o topo é o "porteiro", o menor dos grandes, pronto para ser expulso). K menores → max-heap de tamanho K (o topo é o maior dos pequenos). Guardar só K, e descartar o extremo errado, é o que dá o O(n log k).
🧠 Quiz de fixação
0/41. Para achar os K MAIORES elementos, por que usar um MIN-heap (e não um max-heap)?
2. Por que o heap de tamanho K é O(n log k) e não O(n log n)?
3. Quando o heap de tamanho K é preferível a simplesmente ordenar o array?
4. Como o Top K Frequent combina padrões que você já conhece?
Resumo
- Top-K: mantenha um heap de tamanho K com os K melhores; o topo é o K-ésimo.
- K maiores → min-heap; K menores → max-heap (o topo é o que se descarta).
- O(n log k), O(k) espaço — ganha de ordenar quando K ≪ n ou em fluxos.
- Top K Frequent = hash map (contar) + heap de tamanho K.
Próxima aula: o heap escolhendo o próximo menor entre K fontes — k-way merge.