heapq do Python e Técnicas de Max-Heap
Use heapq.heappush/heappop, negue valores para simular um max-heap e aplique heapq.nlargest/nsmallest a consultas rápidas dos k maiores elementos.
heapq do Python e Técnicas de Max-Heap é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Visão geral do módulo heapq do Python
O módulo heapq do Python fornece um monte mínimo implementado sobre uma lista comum do Python. Diferentemente de uma classe de monte dedicada, heapq opera diretamente em listas existentes. As funções do módulo são: heapify para construir um monte em O(n), heappush para adicionar um elemento em O(log n), heappop para remover o mínimo em O(log n) e heappushpop / heapreplace para obter eficiência combinada.
import heapq
# heapq operates on plain Python lists
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)
print('Heap array:', heap) # internal array (not sorted!)
print('Peek min:', heap[0]) # O(1) min access
print('Pop min:', heapq.heappop(heap)) # 1
print('Next min:', heap[0]) # 2
# heapify: turn any list into a heap in O(n)
data = [9, 4, 7, 1, 3, 6, 2]
heapq.heapify(data)
print('Heapified:', data, '| min:', data[0])Monte máximo por negação dos valores
O heapq do Python fornece apenas um monte mínimo. Para simular um monte máximo, negue todos os valores antes de fazer push e negue-os novamente ao fazer pop. Isso funciona porque o monte ordena pelos valores armazenados, e a negação inverte a ordenação. Lembre-se sempre de negar nos dois lados: negue antes do push e depois do pop. Esquecer qualquer uma dessas etapas é um erro comum em entrevistas.
import heapq
max_heap = []
for val in [5, 1, 8, 3, 9, 2]:
heapq.heappush(max_heap, -val) # negate on push
print('Max-heap internal:', max_heap) # all negated
# Pop in descending order:
results = []
while max_heap:
results.append(-heapq.heappop(max_heap)) # negate on pop
print('Sorted descending:', results) # [9, 8, 5, 3, 2, 1]
# Common pattern: top-k largest
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k = 3
heap = []
for x in data:
heapq.heappush(heap, -x)
print('Top', k, ':', [-heapq.heappop(heap) for _ in range(k)])heapq.nlargest e nsmallest
heapq.nlargest(k, iterable) e heapq.nsmallest(k, iterable) retornam os k maiores ou menores itens. Elas têm complexidade O(n log k), mais eficiente que uma ordenação completa (O(n log n)) quando k é muito menor que n. Internamente, usam um monte de tamanho k. Quando k é próximo de n, o Python recorre à ordenação completa. Use-as para consultas pontuais dos k primeiros elementos sem manter um monte persistente.
import heapq
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 7]
# Top 3 largest:
print(heapq.nlargest(3, data)) # [9, 8, 7]
# Top 3 smallest:
print(heapq.nsmallest(3, data)) # [1, 1, 2]
# With a key function:
words = ['banana', 'apple', 'cherry', 'date', 'elderberry']
print(heapq.nlargest(2, words, key=len)) # ['elderberry', 'banana']
print(heapq.nsmallest(2, words, key=len)) # ['date', 'apple']
# Note: when k ~ n, use sorted() instead:
# sorted(data)[-k:] or sorted(data, reverse=True)[:k]Monte com tuplas para chaves complexas
Quando os elementos do monte precisam de uma chave de comparação personalizada, armazene-os como tuplas (priority, data). O heapq do Python compara as tuplas elemento a elemento, portanto compara primeiro as prioridades. Se as prioridades forem iguais, compara o segundo elemento — isso pode causar erros se os dados não forem comparáveis. O padrão mais seguro é incluir um contador exclusivo como critério de desempate, para evitar comparar diretamente os elementos de dados.
import heapq
import itertools
# Pattern: (priority, counter, item)
# Counter ensures unique tiebreaker, avoids comparing items
counter = itertools.count()
heap = []
def push_task(priority, task):
heapq.heappush(heap, (priority, next(counter), task))
push_task(3, 'low priority task')
push_task(1, 'high priority task')
push_task(2, 'medium priority task')
push_task(1, 'another high priority')
while heap:
pri, cnt, task = heapq.heappop(heap)
print(f'P{pri}: {task}')
# Output in priority order: P1, P1, P2, P3heapq.merge: mesclagem de iteráveis ordenados
heapq.merge(*iterables) mescla de forma tardia vários iteráveis ordenados em uma única saída ordenada, sem carregar todos os dados na memória. Isso equivale a uma mesclagem de K vias usando um monte mínimo de tamanho k e é usado em algoritmos de ordenação externa. A função retorna um iterador, portanto os elementos são produzidos um por vez — ideal para grandes conjuntos de dados ou cenários de transmissão contínua.
import heapq
# Merge multiple sorted lists efficiently
sorted_lists = [
[1, 5, 9],
[2, 6, 8],
[3, 4, 7]
]
# heapq.merge takes sorted iterables and returns a merged sorted iterator
merged = list(heapq.merge(*sorted_lists))
print('Merged:', merged) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
# The k-way merge manually (educational version):
def merge_k_sorted(lists):
heap = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0))
result = []
while heap:
val, list_idx, elem_idx = heapq.heappop(heap)
result.append(val)
if elem_idx + 1 < len(lists[list_idx]):
heapq.heappush(heap, (lists[list_idx][elem_idx+1], list_idx, elem_idx+1))
return result
print('Manual k-way:', merge_k_sorted(sorted_lists))Padrão de exclusão tardia para montes
Quando você precisa remover elementos arbitrários de um monte, mas não conhece o índice deles, use a exclusão tardia: marque os elementos como excluídos em um conjunto separado e ignore-os ao fazer pop. Isso resulta em O(log n) amortizado e evita a complexidade de rastrear índices. Essa é a abordagem padrão no algoritmo de Dijkstra com entradas duplicadas e em simulações de escalonadores de tarefas.
import heapq
class LazyHeap:
def __init__(self):
self._heap = []
self._removed = set()
def push(self, task):
heapq.heappush(self._heap, task)
def remove(self, task):
self._removed.add(task) # mark as removed
def pop(self):
while self._heap:
task = heapq.heappop(self._heap)
if task not in self._removed:
return task
return None
lh = LazyHeap()
for t in [5, 1, 8, 3, 2]:
lh.push(t)
lh.remove(1) # 'delete' 1 lazily
lh.remove(8) # 'delete' 8 lazily
results = [lh.pop() for _ in range(3)]
print(results) # [2, 3, 5] -- 1 and 8 skippedK-ésimo maior elemento em um fluxo
O k-ésimo maior elemento em um fluxo (LeetCode #703) mantém um monte mínimo de tamanho k. A raiz do monte é sempre o k-ésimo maior elemento visto até o momento. Quando um novo número chega: faça push nele e, se o monte ultrapassar o tamanho k, faça pop do mínimo. A raiz é sempre o k-ésimo maior porque há exatamente k-1 elementos maiores que ela no monte.
import heapq
class KthLargest:
def __init__(self, k, nums):
self.k = k
self.heap = []
for num in nums:
self.add(num)
def add(self, val):
heapq.heappush(self.heap, val)
if len(self.heap) > self.k:
heapq.heappop(self.heap) # remove smallest
return self.heap[0] # kth largest = root of min-heap
# k=3, initial=[4,5,8,2]
kl = KthLargest(3, [4, 5, 8, 2])
print(kl.add(3)) # 4 (top 3: 8,5,4 -- kth=4)
print(kl.add(5)) # 5 (top 3: 8,5,5 -- kth=5)
print(kl.add(10)) # 5 (top 3: 10,8,5 -- kth=5)
print(kl.add(9)) # 8 (top 3: 10,9,8 -- kth=8)Encontre K pares com a menor soma
Encontre K pares com as menores somas (LeetCode #373) usa um monte mínimo para gerar os pares em ordem. Comece com todos os pares (nums1[0], nums2[j]) para cada j. Faça pop do mínimo e, para o par removido (nums1[i], nums2[j]), faça push de (nums1[i+1], nums2[j]) — o próximo candidato da mesma coluna de nums2. Esse é um padrão comum para gerar pares ou produtos ordenados com um monte.
import heapq
def k_smallest_pairs(nums1, nums2, k):
if not nums1 or not nums2:
return []
heap = []
# Initialize with pairs (nums1[0], nums2[j])
for j in range(min(k, len(nums2))):
heapq.heappush(heap, (nums1[0] + nums2[j], 0, j))
result = []
while heap and len(result) < k:
total, i, j = heapq.heappop(heap)
result.append([nums1[i], nums2[j]])
if i + 1 < len(nums1):
heapq.heappush(heap, (nums1[i+1] + nums2[j], i+1, j))
return result
print(k_smallest_pairs([1,7,11], [2,4,6], 3))
# [[1,2], [1,4], [1,6]]Escalonador de tarefas com um monte máximo
O escalonador de tarefas (LeetCode #621) pede o tempo mínimo para escalonar n tarefas com um período de resfriamento de n intervalos entre tarefas iguais. Use um monte máximo de frequências de tarefas: a cada intervalo de tempo, escolha a tarefa disponível mais frequente, diminua sua contagem e coloque-a em resfriamento. Processe k=n+1 tarefas por ciclo (ou preencha o restante com tempo ocioso). Essa abordagem gulosa com um monte máximo produz a resposta ideal.
import heapq
from collections import Counter
def least_interval(tasks, n):
freq = Counter(tasks)
heap = [-f for f in freq.values()] # max-heap (negated)
heapq.heapify(heap)
time = 0
while heap:
cycle = n + 1
temp = []
for _ in range(cycle):
if heap:
temp.append(heapq.heappop(heap))
for f in temp:
if f + 1 < 0: # still tasks remaining
heapq.heappush(heap, f + 1)
# Add full cycle or remaining tasks if queue empty
time += cycle if heap else len(temp)
return time
print(least_interval(['A','A','A','B','B','B'], 2)) # 8
print(least_interval(['A','A','A','B','B','B'], 0)) # 6Monte no algoritmo de Dijkstra
A fila de prioridade no algoritmo de Dijkstra é implementada com um monte mínimo. Armazene tuplas (distance, node) e sempre processe primeiro o nó não visitado mais próximo. Quando você fizer pop de um nó cuja distância seja maior que o caminho mínimo atualmente conhecido (uma entrada obsoleta resultante da exclusão tardia), ignore-o. Isso elimina a necessidade de uma operação de redução de chave e mantém a implementação simples, preservando a complexidade O((V + E) log V).
import heapq
def dijkstra(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0
heap = [(0, start)] # (distance, node)
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: # stale entry, skip
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist
graph = {
'A': [('B', 4), ('C', 1)],
'B': [('D', 1)],
'C': [('B', 2), ('D', 5)],
'D': []
}
print(dijkstra(graph, 'A')) # {'A':0,'B':3,'C':1,'D':4}Reorganizar uma string com um monte máximo
Reorganizar uma string (LeetCode #767) pede que você reorganize uma string para que nenhum par de caracteres adjacentes seja igual. Use um monte máximo de (-frequency, char). A cada etapa, faça pop do caractere mais frequente. Se o caractere anterior for igual ao mais frequente, faça pop do segundo mais frequente. Essa abordagem gulosa garante que o caractere mais restrito seja colocado o mais cedo possível.
import heapq
from collections import Counter
def reorganize_string(s):
freq = Counter(s)
heap = [(-f, c) for c, f in freq.items()]
heapq.heapify(heap)
result = []
prev_freq, prev_char = 0, ''
while heap:
freq, char = heapq.heappop(heap)
result.append(char)
# Push back the previous character if still remaining
if prev_freq < 0:
heapq.heappush(heap, (prev_freq, prev_char))
prev_freq, prev_char = freq + 1, char # decrement freq (less negative)
result_str = ''.join(result)
# Verify no adjacent duplicates
return result_str if len(result_str) == len(s) else ''
print(reorganize_string('aab')) # 'aba'
print(reorganize_string('aaab')) # '' (impossible)Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: a API do módulo heapq do Python, incluindo heapify, heappush, heappop, nlargest, nsmallest e merge; a simulação de monte máximo por meio da negação dos valores; e padrões comuns de montes em entrevistas, incluindo processamento dos k primeiros elementos em fluxo, o k-ésimo maior em um fluxo, o escalonador de tarefas e Dijkstra. Em seguida, abordaremos a mediana de um fluxo de dados e a mesclagem de K vias.
Perguntas Frequentes
A aula “heapq do Python e Técnicas de Max-Heap” é grátis?
Sim — o texto completo de “heapq do Python e Técnicas de Max-Heap” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “heapq do Python e Técnicas de Max-Heap”?
Use heapq.heappush/heappop, negue valores para simular um max-heap e aplique heapq.nlargest/nsmallest a consultas rápidas dos k maiores elementos. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “heapq do Python e Técnicas de Max-Heap”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Propriedade de Heap e Representação em Array
- Heapify, Push e Pop do Zero
- heapq do Python e Técnicas de Max-Heap
- Mediana de um Fluxo de Dados e Intercalação em K Vias