Para crear una cola de prioridad en Python, conserva una lista, inserta elementos con heapq.heappush() y extrae el menor con heapq.heappop(). Insertar y retirar cuesta O(log n), mientras que consultar el mínimo en heap[0] cuesta O(1). Como heapq implementa un min-heap, los valores numéricos menores salen primero.

Una cola normal respeta el orden de llegada; una cola de prioridad atiende primero el elemento más urgente. Se utiliza en planificadores, rutas mínimas, tickets de soporte, simulaciones y fusión de flujos. El módulo pertenece a la biblioteca estándar. Para revisar colas y complejidad, consulta estructuras de datos y algoritmos en Python.

Cómo funciona el heap de heapq

Un heap binario mantiene una propiedad: cada padre es menor o igual que sus hijos. La lista subyacente no está totalmente ordenada; solo se garantiza el mínimo en la posición cero. Esta ordenación parcial permite insertar sin ordenar toda la colección después de cada cambio.

import heapq

tareas = []
heapq.heappush(tareas, (2, "generar informe"))
heapq.heappush(tareas, (1, "restaurar servicio"))
heapq.heappush(tareas, (3, "archivar logs"))


while tareas:
prioridad, tarea = heapq.heappop(tareas)
print(prioridad, tarea)

La prioridad 1 aparece primero. Las tuplas se comparan campo a campo, así que el texto desempata prioridades iguales en este ejemplo. La documentación oficial de heapq también describe heapify(), heappushpop(), heapreplace(), nsmallest() y nlargest().

Si los elementos ya están en una lista, heapq.heapify(elementos) la transforma en O(n). Insertar n elementos individualmente cuesta O(n log n). No ordenes después de cada inserción: pagarías por un orden total innecesario. La guía de manejo de listas en Python explica los costes de insertar y desplazar elementos.

Desempates seguros con un contador

Una entrada (prioridad, tarea) puede fallar cuando dos prioridades iguales obligan a comparar objetos sin orden definido. Incluso las cadenas comparables usan un desempate alfabético, no el orden de llegada. Incluye un contador creciente y almacena (prioridad, secuencia, tarea).

import heapq
from dataclasses import dataclass
from itertools import count

@dataclass
class Tarea:
nombre: str
cliente: str


secuencia = count()
cola = []


def agregar(prioridad: int, tarea: Tarea) -> None:
heapq.heappush(cola, (prioridad, next(secuencia), tarea))


agregar(1, Tarea("corregir pago", "Tienda A"))
agregar(1, Tarea("liberar pedido", "Tienda B"))
agregar(2, Tarea("exportar métricas", "Interno"))


while cola:
prioridad, _, tarea = heapq.heappop(cola)
print(prioridad, tarea.nombre)

El contador mantiene el orden de llegada entre prioridades iguales e impide comparar instancias de Tarea. La data class vuelve legible cada registro; la guía de data classes en Python desarrolla valores predeterminados, orden e inmutabilidad.

Atender primero prioridades mayores

Con la interfaz tradicional de min-heap, niega la clave numérica para modelar prioridad máxima. El mayor número original se convierte en el menor almacenado. Niega solo la clave y restáurala al extraer:

import heapq

cola = []
heapq.heappush(cola, (-100, "incidente crítico"))
heapq.heappush(cola, (-20, "consulta comercial"))


prioridad_negativa, ticket = heapq.heappop(cola)
prioridad = -prioridad_negativa
print(prioridad, ticket)  # 100 incidente crítico

Documenta si 1 significa urgente o prioridad baja. Muchos errores proceden de convenciones contradictorias entre productores y consumidores, no del heap. Un Enum aclara niveles discretos; consulta Enum en Python.

Caso real: actualizar y cancelar tareas

heapq no permite buscar, eliminar ni actualizar eficientemente por identificador. Modificar una entrada arbitraria puede romper la propiedad. Los planificadores suelen guardar un diccionario de entradas vigentes, marcar la antigua como eliminada e insertar una sustituta. Las entradas obsoletas se descartan al llegar arriba, técnica llamada eliminación perezosa.

import heapq
from itertools import count

ELIMINADA = object()
heap = []
activas = {}
secuencia = count()


def agregar(id_tarea, prioridad, datos):
if id_tarea in activas:
cancelar(id_tarea)
entrada = [prioridad, next(secuencia), id_tarea, datos]
activas[id_tarea] = entrada
heapq.heappush(heap, entrada)


def cancelar(id_tarea):
entrada = activas.pop(id_tarea)
entrada[3] = ELIMINADA


def retirar():
while heap:
prioridad, _, id_tarea, datos = heapq.heappop(heap)
if datos is not ELIMINADA:
del activas[id_tarea]
return id_tarea, prioridad, datos
raise KeyError("cola vacía")


agregar("job-7", 5, {"tipo": "email"})
agregar("job-7", 1, {"tipo": "email urgente"})
print(retirar())

El diccionario da acceso promedio O(1) a la entrada activa; el heap selecciona la siguiente en O(log n). Las entradas eliminadas ocupan memoria hasta alcanzar la cima. Con muchas actualizaciones y pocas extracciones, reconstruye periódicamente el heap desde las entradas activas.

¿heapq, PriorityQueue o bisect?

heapq es ligero y no sincronizado, ideal para algoritmos y flujos de un hilo. queue.PriorityQueue envuelve un heap con bloqueos y espera para productores y consumidores en hilos. La documentación oficial de queue explica put(), get(), capacidad y task_done(). Varios procesos o workers distribuidos requieren otra infraestructura.

bisect.insort() mantiene una lista completamente ordenada. Encontrar la posición cuesta O(log n), pero desplazar elementos cuesta O(n). Es útil si recorres a menudo todos los elementos en orden o consultas posiciones arbitrarias. La documentación oficial de bisect detalla este compromiso. Si la operación dominante es retirar repetidamente el mínimo, el heap suele ser mejor.

Errores frecuentes

  • Usar append: no restaura la propiedad; usa heappush().
  • Creer que la lista está ordenada: solo heap[0] tiene una posición garantizada.
  • Llamar pop(0): cuesta O(n) y no reorganiza el heap; usa heappop().
  • Ignorar empates: añade un contador antes de objetos no comparables.
  • Modificar prioridades: inserta una sustituta o usa heapify(); aplica eliminación perezosa si es frecuente.
  • Compartir entre hilos: heapq no bloquea; sincroniza el acceso o usa PriorityQueue.

Checklist de implementación

  • Documenta si los números menores o mayores representan más urgencia.
  • Modela entradas como (prioridad, secuencia, elemento).
  • Usa heapify() al cargar un lote existente.
  • Retira con heappop() y trata explícitamente la cola vacía.
  • Planifica cancelación, cambio de prioridad y limpieza de obsoletos.
  • Elige PriorityQueue cuando los hilos deban esperar con seguridad.
  • Prueba empates, vacío, prioridades negativas y volumen realista.

Separa la política de la cola de la ejecución de tareas para probar ambas partes. Las recomendaciones de Clean Code en Python ayudan a evitar convenciones ocultas y workers demasiado grandes.

Preguntas frecuentes

¿heapq crea un min-heap o un max-heap?

La interfaz tradicional crea un min-heap, así que el menor queda arriba. Para extraer primero prioridades numéricas mayores, niega la clave o utiliza las API máximas disponibles en la versión adoptada.

¿Puedo ordenar el heap para mostrar la cola?

Puedes ordenar una copia sin afectar el original. No dependas del orden interno más allá del índice cero. Para consumir en orden, ejecuta heappop() repetidamente sobre una copia.

¿heapq es seguro para hilos?

No proporciona sincronización. Protege el acceso con bloqueos propios o usa queue.PriorityQueue, diseñada para la comunicación segura entre hilos.

¿Cuándo es mejor una lista ordenada?

Cuando recorres todos los elementos en orden, consultas posiciones arbitrarias o manejas muy pocos elementos. Para insertar y retirar repetidamente el extremo prioritario, un heap suele escalar mejor.