heapq de Python y trucos para max-heap
Use heapq.heappush/heappop, niegue los valores para simular un max-heap y aplique heapq.nlargest/nsmallest a consultas rápidas de top-k.
heapq de Python y trucos para max-heap es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
Descripción general del módulo heapq de Python
El módulo heapq de Python proporciona un min-heap implementado sobre una lista normal de Python. A diferencia de una clase de heap específica, heapq opera directamente sobre listas existentes. Las funciones del módulo son: heapify para construir un heap en O(n), heappush para añadir un elemento en O(log n), heappop para eliminar el mínimo en O(log n), y heappushpop / heapreplace para realizar ambas operaciones de forma más eficiente.
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])Max-heap mediante la negación de valores
El heapq de Python solo proporciona un min-heap. Para simular un max-heap, niegue todos los valores antes de hacer push y vuelva a negarlos al hacer pop. Esto funciona porque el heap ordena según los valores almacenados, y la negación invierte el orden. Recuerde siempre negar en ambos lados: niegue antes de hacer push y después de hacer pop. Olvidar cualquiera de estos pasos es un error común en las 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 y nsmallest
heapq.nlargest(k, iterable) y heapq.nsmallest(k, iterable) devuelven los k elementos más grandes o más pequeños. Su complejidad es O(n log k), por lo que son más eficientes que una ordenación completa (O(n log n)) cuando k es mucho menor que n. Internamente utilizan un heap de tamaño k. Cuando k se aproxima a n, Python recurre a la ordenación completa. Utilícelas para consultas top-k puntuales sin mantener un heap 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]Heap con tuplas para claves complejas
Cuando los elementos del heap necesitan una clave de comparación personalizada, almacénelos como tuplas (priority, data). El heapq de Python compara las tuplas elemento por elemento, por lo que primero compara las prioridades. Si las prioridades son iguales, compara el segundo elemento; esto puede causar errores si los datos no se pueden comparar. El patrón más seguro consiste en incluir un contador único como desempate para evitar comparar directamente los elementos de datos.
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: combinación de iterables ordenados
heapq.merge(*iterables) combina de forma perezosa varios iterables ordenados en una única salida ordenada sin cargar todos los datos en memoria. Esto equivale a una combinación en k vías mediante un min-heap de tamaño k y se utiliza en algoritmos de ordenación externa. Devuelve un iterador, por lo que los elementos se producen uno a uno, lo que resulta ideal para conjuntos de datos grandes o escenarios de streaming.
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))Patrón de eliminación diferida para heaps
Cuando necesita eliminar elementos arbitrarios de un heap, pero no conoce su índice, utilice la eliminación diferida: marque los elementos como eliminados en un conjunto independiente y, después, omítalos al hacer pop. Esta operación tiene un coste amortizado de O(log n) y evita la complejidad de realizar un seguimiento de los índices. Es el enfoque estándar en el algoritmo de Dijkstra con entradas duplicadas y en las simulaciones de planificadores de tareas.
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 elemento más grande en un flujo
K-ésimo elemento más grande en un flujo (LeetCode #703) mantiene un min-heap de tamaño k. La raíz del heap siempre es el k-ésimo elemento más grande visto hasta el momento. Cuando llega un número nuevo: insértelo y, si el heap supera el tamaño k, extraiga el mínimo. La raíz siempre es el k-ésimo elemento más grande porque hay exactamente k-1 elementos mayores que él en el heap.
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)Encontrar k pares con la suma más pequeña
Encontrar k pares con las sumas más pequeñas (LeetCode #373) utiliza un min-heap para generar los pares en orden. Comience con todos los pares (nums1[0], nums2[j]) para cada j. Extraiga el mínimo y, para el par extraído (nums1[i], nums2[j]), inserte (nums1[i+1], nums2[j]), el siguiente candidato de la misma columna de nums2. Este es un patrón común para generar pares o productos ordenados con un heap.
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]]Planificador de tareas con un max-heap
Planificador de tareas (LeetCode #621) plantea encontrar el tiempo mínimo para programar n tareas con un período de enfriamiento de n intervalos entre tareas iguales. Utilice un max-heap con las frecuencias de las tareas: en cada paso temporal, seleccione la tarea disponible más frecuente, reduzca su contador y póngala en enfriamiento. Procese k=n+1 tareas por ciclo (o complete el ciclo con tiempo de inactividad). Este enfoque voraz con un max-heap proporciona la respuesta óptima.
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)) # 6Heap en el algoritmo de Dijkstra
La cola de prioridad del algoritmo de Dijkstra se implementa con un min-heap. Almacene tuplas (distance, node) y procese siempre primero el nodo no visitado más cercano. Cuando extraiga un nodo cuya distancia sea mayor que su camino más corto conocido actualmente (una entrada obsoleta causada por la eliminación diferida), omítalo. Esto evita la necesidad de una operación decrease-key y mantiene sencilla la implementación, con una complejidad de 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 una cadena con un max-heap
Reorganizar una cadena (LeetCode #767) le pide reorganizar una cadena para que no haya dos caracteres adyacentes iguales. Utilice un max-heap de (-frequency, char). En cada paso, extraiga el carácter más frecuente. Si el carácter anterior coincide con el más frecuente, extraiga en su lugar el segundo más frecuente. Este enfoque voraz garantiza que el carácter con mayores restricciones se coloque lo antes posible.
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)Comprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido: la API del módulo heapq de Python, incluidos heapify, heappush, heappop, nlargest, nsmallest y merge; la simulación de un max-heap mediante la negación de valores; y patrones habituales de heaps en entrevistas, como top-k en streaming, el k-ésimo elemento más grande en un flujo, el planificador de tareas y Dijkstra. A continuación, abordará la mediana de un flujo de datos y la combinación en k vías.
Preguntas frecuentes
¿La lección «heapq de Python y trucos para max-heap» es gratis?
Sí — el texto completo de «heapq de Python y trucos para max-heap» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «heapq de Python y trucos para max-heap»?
Use heapq.heappush/heappop, niegue los valores para simular un max-heap y aplique heapq.nlargest/nsmallest a consultas rápidas de top-k. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «heapq de Python y trucos para max-heap»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Propiedad del heap y representación en array
- Heapify, push y pop desde cero
- heapq de Python y trucos para max-heap
- Mediana de un flujo de datos y combinación k-way