El módulo heapq implementa heaps binarios sobre listas Python. Un heap mantiene el elemento menor en la posición cero y permite insertar o retirar prioridades en tiempo logarítmico. Esta estructura es útil en colas de prioridad, caminos mínimos, scheduling, simulaciones, procesamiento de eventos y selección de los mayores o menores valores de un flujo.
Un heap no es una lista totalmente ordenada. Solo se garantiza la relación entre padres e hijos. Recorrer la lista interna no produce elementos en orden ascendente. Usa las operaciones del módulo y trata la representación como detalle interno.
Crea un heap vacío
Un heap comienza como una lista normal.
import heapq
cola = []
heapq.heappush(cola, 5)
heapq.heappush(cola, 2)
heapq.heappush(cola, 8)
print(cola[0])
El menor valor está en cola[0], pero las demás posiciones no están completamente ordenadas.
Retira el menor elemento
heappop() elimina y devuelve la entrada menor.
while cola:
print(heapq.heappop(cola))
Retirar de un heap vacío lanza IndexError. Comprueba la condición o trata el caso esperado.
Construye con heapify
heapify() reorganiza una lista existente en tiempo lineal.
valores = [9, 1, 7, 3, 2]
heapq.heapify(valores)
Es más eficiente que insertar cada elemento si todos ya están disponibles.
Colas de prioridad con tuplas
Las tuplas se comparan campo a campo. Un patrón común almacena prioridad y payload.
cola = []
heapq.heappush(cola, (10, "informe"))
heapq.heappush(cola, (1, "alarma"))
prioridad, tarea = heapq.heappop(cola)
Los números menores salen primero. Para prioridad mayor primero, niega valores numéricos o usa APIs de max-heap disponibles en la versión objetivo.
Empates y estabilidad
Si las prioridades empatan, Python compara el segundo campo. Tareas no comparables pueden lanzar TypeError.
from itertools import count
contador = count()
heapq.heappush(cola, (prioridad, next(contador), tarea))
El contador conserva el orden de inserción entre prioridades iguales.
No compares tareas directamente
Objetos de dominio, diccionarios y callbacks no deberían participar en el orden.
Usa (prioridad, secuencia, item) o una dataclass con campos comparables controlados.
heappushpop
heappushpop() inserta un elemento y retira el menor en una sola operación.
retirado = heapq.heappushpop(heap, nuevo_item)
Es eficiente para mantener los N mayores valores observados.
heapreplace
heapreplace() retira primero el menor y después inserta el nuevo.
antiguo = heapq.heapreplace(heap, nuevo_item)
El resultado difiere de heappushpop() cuando el nuevo valor es menor que la raíz.
Mantén los mayores N
Usa un min-heap de tamaño fijo.
limite = 100
heap = []
for valor in stream:
if len(heap) < limite:
heapq.heappush(heap, valor)
elif valor > heap[0]:
heapq.heapreplace(heap, valor)
Al final contiene los mayores valores, pero no están ordenados.
nsmallest y nlargest
nsmallest() y nlargest() seleccionan extremos.
top = heapq.nlargest(10, registros, key=lambda item: item.puntuacion)
Para N pequeño pueden ser mejores que ordenar todo. Cuando N se acerca al total, sorted() puede ser más simple y rápido.
Funciones key
Las funciones de selección aceptan key, pero heappush() no.
En un heap persistente, incluye la clave calculada en la tupla para no recalcularla.
Merge de streams ordenados
heapq.merge() combina iterables ya ordenados de forma lazy.
resultado = heapq.merge(archivo_a, archivo_b, key=extraer_clave)
for item in resultado:
procesar(item)
Todas las entradas deben usar la misma regla de orden.
Actualiza prioridades
El módulo no ofrece decrease-key directo. Modificar una entrada dentro de la lista puede romper el heap.
Una estrategia segura inserta una entrada nueva y marca la anterior como eliminada.
ELIMINADO = object()
entradas = {}
def agregar(item, prioridad):
if item in entradas:
eliminar(item)
entrada = [prioridad, next(contador), item]
entradas[item] = entrada
heapq.heappush(cola, entrada)
def eliminar(item):
entrada = entradas.pop(item)
entrada[2] = ELIMINADO
Retira entradas válidas
def retirar():
while cola:
prioridad, secuencia, item = heapq.heappop(cola)
if item is not ELIMINADO:
del entradas[item]
return item
raise KeyError("cola vacía")
Las entradas obsoletas consumen memoria hasta llegar a la raíz. Reconstruye el heap periódicamente si hay muchas actualizaciones.
Max-heaps
El patrón tradicional para máximos es negar prioridades numéricas.
heapq.heappush(cola, (-prioridad, secuencia, item))
No niegues valores no numéricos. Revisa también las APIs específicas disponibles en la versión mínima.
Complejidad
heappush() y heappop() son O(log n), consultar la raíz es O(1) y heapify() es O(n).
Estas garantías no incluyen comparaciones costosas o payloads grandes.
Algoritmos de grafos
Las colas de prioridad aparecen en Dijkstra, A*, Prim y simulaciones.
Sin decrease-key, inserta nuevas distancias e ignora entradas antiguas al retirarlas. En Dijkstra, valida pesos no negativos.
Scheduling de eventos
Un heap puede almacenar (instante, secuencia, callback).
heapq.heappush(eventos, (cuando, next(contador), callback))
Usa un reloj monotónico y no ejecutes callbacks largos mientras mantienes un lock.
Threads
heapq no sincroniza accesos. Varias threads necesitan lock o queue.PriorityQueue.
concurrent.futures en Python ayuda a coordinar workers, pero la cola necesita capacidad y shutdown.
Backpressure
Una cola ilimitada puede crecer hasta agotar memoria.
Define capacidad, rechazo, persistencia o descarte de baja prioridad.
Prioridades mutables
Si la prioridad depende de un atributo que cambia después de insertar, el orden se vuelve incorrecto.
Guarda una clave inmutable y actualiza mediante reinserción.
Salida ordenada
Retira repetidamente para obtener orden o usa sorted(heap) si ya no necesitas conservarlo.
Recorrer la lista interna no produce orden completo.
Persistencia
Serializar la lista interna expone detalles y entradas obsoletas.
Guarda tareas lógicas con prioridades y reconstruye mediante heapify().
Seguridad
Prioridades externas pueden monopolizar la capacidad o provocar starvation. Aplica autorización, cuotas y clases de servicio.
No ejecutes callbacks de fuentes no confiables.
Pruebas
Prueba cola vacía, empates, prioridades negativas, actualizaciones, cancelación, entradas eliminadas, top-k, volumen y concurrencia.
Compara resultados con sorted() en tests de propiedades.
Errores comunes
Los fallos frecuentes son asumir que la lista está ordenada, comparar tareas incompatibles, modificar prioridades en el lugar, confundir heapreplace() y heappushpop(), olvidar estabilidad y permitir crecimiento ilimitado.
Conclusión
heapq implementa colas de prioridad eficientes sobre listas. Usa tuplas con prioridad y secuencia, claves inmutables y lazy deletion para actualizaciones.
Consulta la documentación oficial de heapq, concurrent.futures en Python y el próximo artículo sobre bisect.
