El módulo heapq es una de las herramientas más útiles de la biblioteca estándar para implementar colas de prioridad. Durante muchos años, su interfaz pública estuvo orientada principalmente a min-heaps, donde el valor menor permanece en la parte superior. Las versiones recientes de Python incorporaron operaciones explícitas para max-heaps, lo que hace el código más claro cuando el elemento mayor debe tener prioridad. En esta guía aprenderás a crear, actualizar y consumir estos heaps de forma segura.
Qué es un heap
Un heap es una estructura parcialmente ordenada. En un min-heap, el primer elemento es el menor. En un max-heap, el primero es el mayor. La lista completa no está ordenada, y el programa nunca debe asumir que lo está. La ventaja es que insertar y retirar el elemento prioritario cuesta tiempo logarítmico sin ordenar toda la colección después de cada cambio.
Los heaps son adecuados para planificadores, colas de tareas, algoritmos de grafos, simulaciones, procesamiento de eventos, rankings y sistemas donde las prioridades cambian continuamente.
Por qué una API nativa de max-heap es mejor
Antes de contar con funciones específicas, era habitual negar prioridades numéricas. Los valores 10, 20 y 30 se almacenaban como -10, -20 y -30 para que el min-heap mostrara primero el mayor valor original. La técnica funciona, pero reduce la legibilidad y se vuelve incómoda con tuplas, objetos personalizados y datos no numéricos.
import heapq
prioridades = [10, 30, 20, 50, 40]
heapq.heapify_max(prioridades)
print(prioridades[0]) # 50
heapify_max transforma una lista existente en el mismo objeto. Su complejidad lineal suele ser mejor que insertar cada elemento individualmente cuando todos los datos ya están disponibles.
Insertar valores
Después de construir el heap, utiliza heappush_max para añadir un valor y conservar la propiedad de max-heap.
heapq.heappush_max(prioridades, 60)
print(prioridades[0]) # 60
La función no ordena toda la lista. Solo desplaza el nuevo elemento por los niveles necesarios, por lo que su coste habitual es O(log n).
Retirar el valor mayor
heappop_max elimina y devuelve el elemento más grande.
mayor = heapq.heappop_max(prioridades)
print(mayor)
La operación también cuesta O(log n). En una cola real, el elemento retirado puede representar la incidencia más urgente, la puntuación más alta o el evento con mayor peso.
Reemplazo eficiente
Cuando necesitas retirar el máximo actual e insertar otro valor inmediatamente, heapreplace_max combina ambas acciones.
retirado = heapq.heapreplace_max(prioridades, 25)
El máximo anterior se retira antes de insertar el nuevo valor. El reemplazo puede ser mayor o menor que el dato devuelto, por lo que conviene verificar que este orden coincide con el algoritmo.
Push y pop en una operación
heappushpop_max considera primero el nuevo elemento y después retira el máximo de forma optimizada.
retirado = heapq.heappushpop_max(prioridades, 35)
Es útil para ventanas de tamaño fijo y algoritmos de selección. No es equivalente a heapreplace_max: en una función el elemento nuevo participa en la elección del máximo, mientras que en la otra primero se elimina el máximo anterior.
Cola de tareas con prioridad
Las aplicaciones reales suelen almacenar tuplas. El primer campo define la prioridad y los siguientes resuelven empates y contienen los datos.
import heapq
from itertools import count
contador = count()
cola = []
def agregar(prioridad, nombre):
heapq.heappush_max(cola, (prioridad, -next(contador), nombre))
def siguiente():
prioridad, _, nombre = heapq.heappop_max(cola)
return prioridad, nombre
agregar(5, "generar informe")
agregar(10, "resolver caída")
agregar(7, "revisar registros")
print(siguiente())
El contador evita que Python compare directamente nombres u objetos cuando las prioridades empatan. En un max-heap debes elegir con cuidado el signo del contador para conservar el orden deseado.
Objetos personalizados
Las dataclasses ordenables permiten crear entradas más expresivas.
from dataclasses import dataclass, field
@dataclass(order=True)
class Tarea:
prioridad: int
secuencia: int
descripcion: str = field(compare=False)
Solo los campos comparables participan en el orden. Si dos objetos no se pueden comparar de forma consistente, las operaciones del heap lanzarán TypeError. Prueba siempre las prioridades duplicadas.
Elegir min-heap o max-heap
Utiliza min-heap cuando el menor plazo, coste o distancia deba procesarse primero. Utiliza max-heap cuando la mayor puntuación, urgencia, carga o ganancia tenga prioridad. A veces un min-heap pequeño es la mejor forma de conservar los N valores mayores; en otros casos, un max-heap refleja directamente la regla del dominio.
Para reforzar las bases, consulta estructuras de datos en Python, listas en Python, tuplas en Python y funciones en Python.
Errores frecuentes
El primer error es tratar la lista interna como si estuviera ordenada. Solo el elemento superior tiene una garantía directa. El segundo es mezclar funciones de min-heap y max-heap sobre la misma lista. El tercero es modificar la prioridad de un elemento interno sin restaurar la propiedad del heap. Retira y vuelve a insertar el dato, reconstruye el heap o utiliza invalidación diferida.
Los valores NaN, los campos mutables y las comparaciones inconsistentes también producen resultados sorprendentes. En código concurrente, protege la estructura con sincronización o usa una abstracción de nivel superior.
Rendimiento y pruebas
Prueba el heap vacío, un único valor, prioridades repetidas, entradas ya ordenadas, orden inverso y grandes volúmenes. Retirar de un heap vacío genera IndexError. Valida la entrada controlada por usuarios y documenta cómo se resuelven los empates.
La documentación oficial de heapq es la referencia principal. Para comprender la teoría, consulta la explicación de la estructura de montículo.
Conclusión
Las funciones nativas de max-heap hacen que el código de prioridades sea más legible y mantenible. heapify_max, heappush_max, heappop_max, heapreplace_max y heappushpop_max cubren creación, inserción, retirada y reemplazo. La elección depende del orden exacto de las operaciones y de si el heap debe conservar un tamaño fijo. Con desempates explícitos, comparaciones estables y una estrategia clara para actualizar prioridades, los max-heaps son una base eficiente para planificadores, rankings, colas y algoritmos de selección.
