Encontre os k maiores com heaps
Use uma fila de prioridade para obter rapidamente os menores ou maiores itens.
- Explicar o que um heap garante.
- Resolver problemas de top-k em O(n log k).
- Usar o módulo heapq do Python.
Um heap (fila de prioridade) deixa o seu menor item disponível na hora, no topo. Acrescentar um item e remover o topo levam O(log n) cada. Os heaps brilham sempre que você precisa repetidamente do “próximo menor” ou dos “k maiores” sem ordenar tudo: elementos top-k, mesclar k listas ordenadas, agendamento e o caminho mais curto de Dijkstra.
Heaps em Python
heapqimplementa um min-heap numa lista comum:heappush(h, x),heappop(h)eh[0]para espiar o topo.- Para um max-heap, empilhe valores negados ou use tuplas
(-priority, item). heapq.nlargest(k, items)eheapq.nsmallest(k, items)resolvem o top-k diretamente.- Truque do top-k: mantenha um min-heap de tamanho k. Para cada item novo, acrescente-o; se o heap passar de k, remova o menor. No fim, o heap guarda os k maiores, em tempo O(n log k).
1import heapq
2
3def k_largest(nums, k):
4 heap = []
5 for num in nums:
6 heapq.heappush(heap, num)
7 if len(heap) > k:
8 heapq.heappop(heap) # drop the smallest
9 return sorted(heap, reverse=True)
10
11print(k_largest([3, 1, 5, 12, 2, 11], 3))[12, 11, 5]
Por que um min-heap para os maiores itens? O topo do heap é o menor dos k maiores atuais - o que deve sair quando chegar algo maior. Ordenar tudo seria O(n log n); o heap de tamanho k é O(n log k), o que importa quando k é bem menor que n.
Principais conclusões
Os heaps dão push/pop em O(log n) e espiada no mínimo em O(1).
Mantenha um min-heap de tamanho k para encontrar os k maiores em O(n log k).
Negue os valores para ter um max-heap em Python.
Quiz da aula
5 perguntas · aprovação com 4 acertos · até 50 XP
Ao passar, você conclui a aula e mantém sua sequência. As perguntas erradas voltarão em sessões de revisão.
Pratique: resolva problemas de entrevistas técnicas
Resolva um problema clássico de entrevista em Python e execute-o com casos de teste. Busque a complexidade ideal e depois confira os casos extremos. Os exercícios rodam localmente no navegador.
Encontre as k palavras mais frequentes
Leia k e depois uma linha de palavras. Imprima as k palavras mais frequentes, uma por linha, da mais para a menos frequente. Desempate em ordem alfabética.
- As duas primeiras
- Desempate alfabético
O Python é executado em um ambiente isolado no navegador, com limite de 60 segundos. O runtime é carregado pelo CDN do Pyodide; seu código permanece neste navegador.
Dúvidas sobre esta lição
Travou em algum ponto? Pergunte. Descobriu algo? Compartilhe. Explicar também é uma ótima forma de aprender.
Carregando publicações…