2.38. Colas de prioridad¶

Una cola de prioridad es un contenedor que siempre sabe cuál de sus elementos es el más pequeño (o el más grande) sin necesidad de ordenar todo el conjunto. heapq implementa una en MicroPython usando una list corriente como almacenamiento y un algoritmo basado en árboles llamado min-heap para mantener el elemento más pequeño en el índice 0.

2.38.1. El modelo mental¶

Un min-heap es una lista organizada de modo que el elemento en cada índice es menor o igual que los elementos en los índices 2*i + 1 y 2*i + 2. Esa organización hace que tres operaciones sean económicas:

Encontrar el elemento más pequeño: está en heap[0]. Una sola consulta de índice, sin recorrido.
Añadir un elemento: asciende a través del árbol, comparándose con un padre por nivel. Mil elementos suponen unas diez comparaciones; un millón, unas veinte.
Eliminar el elemento más pequeño: el mismo recorrido a la inversa, con el mismo puñado de comparaciones.

La lista no está ordenada. Iterar sobre ella devuelve los elementos en orden arbitrario. Solo se garantiza que heap[0] sea el mínimo.

2.38.2. Las tres funciones en MicroPython¶

El módulo heapq de MicroPython expone exactamente tres funciones:

heapq.heappush(): inserta un elemento manteniendo intacta la invariante del heap.
heapq.heappop(): elimina y devuelve el elemento más pequeño.
heapq.heapify(): reorganiza una lista existente convirtiéndola en un heap en su sitio.

Esa es toda la superficie. heappushpop, heapreplace, nlargest, nsmallest y merge de CPython no existen; los patrones a continuación muestran cómo construir los más comunes a mano.

Empezando desde cero:

>>> import heapq
>>> heap = []
>>> heapq.heappush(heap, 5)
>>> heapq.heappush(heap, 1)
>>> heapq.heappush(heap, 3)
>>> heap
[1, 5, 3]
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
3
>>> heapq.heappop(heap)
5

Empezando a partir de datos existentes:

>>> samples = [5, 1, 3, 2, 4]
>>> heapq.heapify(samples)
>>> samples
[1, 2, 3, 5, 4]
>>> heapq.heappop(samples)
1

Heapificar recorre cada elemento una sola vez y es notablemente más rápido que insertar los mismos elementos uno a uno.

2.38.3. Los N mayores sobre un flujo¶

Un uso natural de una cola de prioridad: hacer un seguimiento de los N elementos más grandes de un flujo que solo puedes leer una vez.

El truco consiste en mantener un min-heap de tamaño N. Cada nuevo valor se inserta; si el heap crece más allá de N, se descarta el más pequeño. El más pequeño siempre está en heap[0], por lo que una sola comparación decide si conservar o descartar cada elemento entrante:

def top_n_brightest(readings, n):
    heap = []
    for r in readings:
        if len(heap) < n:
            heapq.heappush(heap, r)
        elif r > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, r)
    return sorted(heap, reverse=True)

El heap nunca crece más allá de N, por lo que cada valor entrante cuesta el mismo puñado de comparaciones sin importar lo largo que sea el flujo. El sorted final es el único paso cuyo coste depende directamente de N.

2.38.4. Eventos programados¶

Una cola de prioridad de tuplas (deadline, payload) es la forma estándar de un planificador de eventos. Las tuplas se comparan lexicográficamente, así que la tupla con el plazo más pequeño asciende a la cima automáticamente:

import heapq
import time

queue = []
heapq.heappush(queue, (time.time() + 5, 'check sensors'))
heapq.heappush(queue, (time.time() + 1, 'blink LED'))
heapq.heappush(queue, (time.time() + 3, 'send heartbeat'))

while queue:
    deadline, task = queue[0]
    now = time.time()
    if now < deadline:
        time.sleep(deadline - now)
    heapq.heappop(queue)
    run(task)

Si dos eventos comparten un plazo, la comparación de tuplas pasa al segundo elemento. Para cargas útiles que no son comparables de forma natural, añade un contador como segundo elemento de la tupla para forzar un orden estable:

counter = 0
def schedule(deadline, task):
    global counter
    counter += 1
    heapq.heappush(queue, (deadline, counter, task))

Ahora el comportamiento de plazo-más-pequeño-primero permanece intacto, los empates se resuelven con el contador para que las tareas programadas antes se ejecuten primero, y task no tiene por qué ser comparable.

2.38.5. Lo que `heapq` no te ofrece¶

Unos cuantos patrones que parecen que deberían funcionar, pero no:

Iterar con for x in heap no produce una salida ordenada: el orden subyacente de la lista es la disposición en árbol del heap. Para consumir el heap en orden, usa heappop hasta vaciarlo.
No hay forma de cambiar la prioridad de un elemento que ya está en el heap. La solución habitual es insertar la nueva prioridad como una entrada nueva y marcar la antigua como cancelada (omitirla cuando salga).
El heap almacena referencias a sus elementos, no copias. Mutar un elemento después de insertarlo puede romper la invariante del heap. Usa valores inmutables (números, tuplas) como clave de comparación.

Un min-heap sobre una lista corriente es la herramienta adecuada para cualquier pregunta del tipo «cuál es el más pequeño» o «cuál es el más urgente» en un dispositivo embebido pequeño. Tres funciones, una lista, y el heap se encarga del resto.