Heaps binarios y colas de prioridad

Qué cubre este capítulo

Un heap binario es la cola de prioridad: la estructura para "dame siempre lo más importante primero, y sigue haciéndolo mientras las cosas entran y salen". Lo logra manteniendo un orden mucho más débil que el de un árbol de búsqueda: no está ordenado del todo, nomás cumple "cada padre le gana a sus hijos", lo cual basta para garantizar que el elemento más chico (o más grande) siempre esté en la raíz. Esa promesa más floja es más barata de mantener, así que asomarse al extremo es O(1) e insertar o eliminar es O(log n). Ya conociste su truco de array-como-árbol en heapsort; aquí lo construimos como estructura independiente y lo conectamos con Dijkstra, la codificación de Huffman y todos los schedulers.

Un poco de historia

El heap binario llegó en 1964 junto con heapsort: J. W. J. Williams introdujo la estructura específicamente para ordenar, y Robert Floyd enseguida demostró que podías construir uno en tiempo lineal. Pero el heap se salió del molde del ordenamiento casi de inmediato, porque resultó ser la implementación natural de una idea que lo precede: la cola de prioridad, una colección donde cada elemento trae una prioridad y siempre sacas el más urgente. Las colas de prioridad ya se usaban para agendar trabajos y mover simulaciones de eventos discretos, y el heap les dio una casa eficiente. La combinación quedó como estándar desde entonces: cuando el algoritmo de caminos más cortos de Edsger Dijkstra necesita "el nodo no visitado más cercano", o la compresión de Huffman necesita "los dos símbolos menos frecuentes", o un sistema operativo necesita "el proceso listo con mayor prioridad", la respuesta es un heap binario. Es la misma estructura que Williams armó para ordenar, reconvertida en el motor de la planificación.

La intuición

Un heap es un árbol binario completo — se llena nivel por nivel, de izquierda a derecha, sin huecos — y como está completo, cabe perfecto en un array sin desperdiciar espacio y sin punteros: los hijos del índice i están en 2i+1 y 2i+2, y su padre en (i−1)//2. Encima de esa forma va una sola regla, la propiedad de heap: cada nodo es menor o igual que sus hijos (en un min-heap). Es una afirmación mucho más débil que la de un árbol de búsqueda — no dice nada sobre izquierda contra derecha, nada sobre hermanos — pero dice justo lo que necesitas: el mínimo no tiene ningún nodo más chico arriba de él, así que el mínimo es la raíz.

Mantener esa regla mientras los elementos llegan y se van son dos movimientos chiquitos. Para insertar, dejas el valor nuevo en la siguiente hoja libre y lo subes (sift up): mientras sea menor que su padre, los intercambias, trepando hasta que se acomoda. Para eliminar el mínimo, tomas la raíz (esa es tu respuesta), mueves la última hoja a la raíz para mantener el árbol completo, y la bajas (sift down): mientras sea mayor que su hijo más chico, la intercambias con ese hijo, hundiéndola hasta que se acomoda. Cada movimiento recorre como máximo la altura del árbol, log n, así que ambos son O(log n). La debilidad del orden es la fuerza de la estructura: como solo comparas a lo largo de un camino raíz-a-hoja, el heap hace muchísimo menos trabajo que una estructura totalmente ordenada para sostener su única garantía.

Complejidad: cómo escala

Asomarse al mínimo es $O(1)$ — es nomás la raíz. Push y pop son $O(\log n)$, un solo recorrido de sift por un camino raíz-a-hoja. Construir un heap desde n elementos existentes de un jalón es $O(n)$, no $O(n \log n)$ — el sorprendente resultado lineal del capítulo de heapsort, porque la mayoría de los nodos están cerca del fondo y casi no bajan. El espacio es $O(n)$, y como es un array empacado, ese espacio es compacto y amigable con el cache. La gráfica corre un stream largo de pushes y pops contra heapq:

Las dos líneas son casi lineales — n operaciones a O(log n) cada una — con heapq unas trece veces más rápido en la constante, por estar en C.

En qué es bueno y en qué no

El heap es la estructura correcta siempre que necesites, una y otra vez, el elemento más extremo de un conjunto que va cambiando. Eso cubre muchísimo terreno: algoritmos voraces que siempre toman la mejor opción disponible (Dijkstra, Prim, Huffman), schedulers y simuladores de eventos que procesan el siguiente deadline más próximo, consultas top-k que mantienen un heap con los k mejores vistos, y mezclar muchos streams ordenados avanzando siempre el que tiene el frente más chico. Su peek en $O(1)$ y sus actualizaciones en $O(\log n)$ son exactamente el perfil que esos problemas piden, y su layout de array empacado lo hace rápido y compacto.

Lo que no es, es una estructura de búsqueda general. El heap encuentra el mínimo al instante pero no sabe casi nada del resto de los elementos: localizar un valor arbitrario, o eliminar uno que no sea el extremo, es $O(n)$, porque tendrías que escanear. Tampoco está ordenado: si haces pop de todo obtienes orden ordenado (eso es heapsort), pero el heap en memoria solo está parcialmente ordenado. Si necesitas iteración ordenada, rangos o búsquedas arbitrarias, eso es un árbol de búsqueda balanceado, no un heap. El heap cambia todas sus capacidades menos una con tal de hacer esa única — agarrar el extremo — lo más rápido posible.

Los datos, o las entradas

El duelo corre un stream largo de pushes y pops intercalados al azar, cronometrado contra heapq. La animación usa un min-heap de siete elementos, dibujado como árbol, y muestra un push subiendo un valor chiquito hasta la raíz, y luego un pop bajando un valor de vuelta — los dos movimientos que son la estructura entera.

Constrúyelo, una función a la vez

Push agrega en la siguiente hoja y sube hasta que se cumple la propiedad de heap:

def push(self, value, probe=None):
    """O(log n): append the value at the end (the next open leaf), then SIFT UP —
    while it's smaller than its parent, swap them — until the heap order (parent ≤
    children) is restored. It bubbles up at most the height of the tree, log n."""
    a = self._a
    a.append(value)
    i = len(a) - 1
    while i > 0:
        parent = (i - 1) // 2
        if a[parent] <= a[i]:
            break
        a[parent], a[i] = a[i], a[parent]
        i = parent
        if probe is not None:
            probe.append({"arr": list(a), "active": i})
    if probe is not None and not a[:i]:
        probe.append({"arr": list(a), "active": i})

Pop devuelve la raíz, sube la última hoja y la baja pasando por su hijo más chico:

def pop(self, probe=None):
    """O(log n): the minimum is always at the root, index 0. Return it, move the
    last element into the root, then SIFT DOWN — swap it with its smaller child
    repeatedly — until heap order holds again over the shrunk heap."""
    a = self._a
    if not a:
        raise IndexError("pop from empty heap")
    top = a[0]
    last = a.pop()
    if a:
        a[0] = last
        i, n = 0, len(a)
        while True:
            left, right, smallest = 2 * i + 1, 2 * i + 2, i
            if left < n and a[left] < a[smallest]:
                smallest = left
            if right < n and a[right] < a[smallest]:
                smallest = right
            if smallest == i:
                break
            a[i], a[smallest] = a[smallest], a[i]
            i = smallest
            if probe is not None:
                probe.append({"arr": list(a), "active": i})
    return top

Míralo funcionar

Aquí tienes un min-heap dibujado como árbol — cada padre más chico que sus hijos, el mínimo (2) en la raíz. Observa dos operaciones. Primero un push de 1: cae hasta abajo como hoja nueva, luego sube, intercambiándose con cada padre que sea mayor que él (el naranja marca el valor viajero), trepando hasta convertirse en la nueva raíz. Después un pop: la raíz se va, la última hoja sube a llenar el hueco, y baja, intercambiándose con su hijo más chico hasta acomodarse. Dos caminos, cada uno de la altura del árbol — eso es el O(log n). Fíjate que el heap nunca está totalmente ordenado; solo mantiene cada padre por debajo de sus hijos, que es todo lo que necesita:

El código completo

Las dos versiones en un solo lugar — cambia entre ellas. La pestaña desde cero es nuestro MinHeap con sift-up y sift-down. La pestaña de librería es heapq, el heap binario en C que usarías de verdad — un conjunto de funciones (heappush, heappop, heapify) sobre una lista común y corriente en vez de una clase.

"""The binary heap — the priority queue. It gives up the search tree's full ordering
for a much weaker one, "every parent beats its children," and in exchange makes one
operation as fast as possible: always hand back the smallest (or largest) element, and
keep doing so as items come and go, all in O(log n).

You already met its trick in heapsort: a complete binary tree flattened into an array,
where node i's children live at 2i+1 and 2i+2, so it needs no pointers. Here it stands
on its own as the structure behind Dijkstra, Huffman coding, event simulation, and every
"process the highest-priority thing next" system.
"""


class MinHeap:
    def __init__(self):
        self._a = []

    # region: push
    def push(self, value, probe=None):
        """O(log n): append the value at the end (the next open leaf), then SIFT UP —
        while it's smaller than its parent, swap them — until the heap order (parent ≤
        children) is restored. It bubbles up at most the height of the tree, log n."""
        a = self._a
        a.append(value)
        i = len(a) - 1
        while i > 0:
            parent = (i - 1) // 2
            if a[parent] <= a[i]:
                break
            a[parent], a[i] = a[i], a[parent]
            i = parent
            if probe is not None:
                probe.append({"arr": list(a), "active": i})
        if probe is not None and not a[:i]:
            probe.append({"arr": list(a), "active": i})
    # endregion

    # region: pop
    def pop(self, probe=None):
        """O(log n): the minimum is always at the root, index 0. Return it, move the
        last element into the root, then SIFT DOWN — swap it with its smaller child
        repeatedly — until heap order holds again over the shrunk heap."""
        a = self._a
        if not a:
            raise IndexError("pop from empty heap")
        top = a[0]
        last = a.pop()
        if a:
            a[0] = last
            i, n = 0, len(a)
            while True:
                left, right, smallest = 2 * i + 1, 2 * i + 2, i
                if left < n and a[left] < a[smallest]:
                    smallest = left
                if right < n and a[right] < a[smallest]:
                    smallest = right
                if smallest == i:
                    break
                a[i], a[smallest] = a[smallest], a[i]
                i = smallest
                if probe is not None:
                    probe.append({"arr": list(a), "active": i})
        return top
    # endregion

    def peek(self):
        """O(1): the minimum is always the root — the heap's whole reason to exist."""
        if not self._a:
            raise IndexError("peek at empty heap")
        return self._a[0]

    def __len__(self):
        return len(self._a)

    def as_list(self):
        return list(self._a)

"""Python's `heapq` is a binary min-heap over a plain list — exactly this structure, in
C. It's a module of functions rather than a class (`heappush`, `heappop`, `heapify`),
operating on a list you own. It's the priority queue you actually use, and the standard
way to answer "smallest/largest so far" and to run Dijkstra and friends.

The face-off is our MinHeap against `heapq` on the same stream of push/pop operations.
"""
import heapq


# region: heapq_ops
def run_ops_heapq(ops):
    """Drive ('push', x) / ('pop',) on a heapq-managed list."""
    h = []
    out = []
    for op in ops:
        if op[0] == "push":
            heapq.heappush(h, op[1])
        else:
            out.append(heapq.heappop(h))
    return out
# endregion

Desde cero contra librería

Nuestro MinHeap y heapq son la misma estructura con las mismas operaciones O(log n), así que la diferencia es la constante de siempre — unos 13× en 400000 operaciones, objetos y llamadas a métodos de Python contra C sobre una lista cruda. Usarías heapq, siempre. Lo valioso de construirlo es que la cola de prioridad deja de ser una caja negra: cuando Dijkstra hace push de tuplas (distance, node) y saca la más cercana, ya sabes que está recorriendo un camino de un array empacado; cuando ves heapq.nlargest, sabes que está manteniendo un heap chiquito; y cuando alguien pregunte por qué no puedes cambiar eficientemente la prioridad de un elemento a medio heap, sabes que es porque el heap solo rastrea el orden padre-hijo y tendría que buscar para encontrar el elemento. La estructura es simple; sus consecuencias atraviesan la mitad de los algoritmos que vienen.

Dónde te lo vas a encontrar de verdad

El heap es la cola de prioridad detrás de una enorme cantidad de infraestructura. Los algoritmos de Dijkstra y Prim (en los capítulos de grafos que vienen) usan uno para expandir siempre el nodo más cercano — es la diferencia entre que esos algoritmos sean rápidos o sean cuadráticos. La codificación de Huffman construye un árbol de compresión óptimo mezclando repetidamente los dos símbolos menos frecuentes sacados de un heap. Los schedulers de sistemas operativos y los simuladores de eventos discretos sacan el siguiente evento por tiempo. Los nlargest/nsmallest y las consultas de "top-k en tendencia" que ves por todos lados son heaps de tamaño k. Mezclar k archivos o streams ordenados — el paso de ordenamiento externo del capítulo de merge sort — usa un heap con los frentes de cada stream. Cada vez que un sistema dice "atiende primero lo más urgente", es muy probable que abajo haya un heap binario.

Puntos clave

Un heap binario es un árbol binario completo empacado en un array con la regla "cada padre le gana a sus hijos", lo que da acceso $O(1)$ al extremo y push y pop en $O(\log n)$ mediante sift-up y sift-down. Su orden parcial es débil a propósito — apenas lo suficiente para mantener el mínimo en la raíz — y por eso es la estructura más barata posible para la única pregunta que responde e inútil para todas las demás. Es la cola de prioridad, heapq en Python, y el motor de los algoritmos voraces de grafos que vienen.

El bloque de árboles ahora deja atrás estas estructuras ordenadas de propósito general y pasa a árboles especializados, cada uno moldeado para un tipo de dato o de consulta. El siguiente capítulo, el trie, es un árbol indexado no por valores completos sino por los caracteres de las cadenas — compartiendo prefijos comunes en ramas compartidas — que es lo que lo vuelve la estructura detrás del autocompletado, los correctores ortográficos y el ruteo IP.