Montículo binario explicado: colas de prioridad, código y complejidad

Qué problema resuelve un montículo

Muchos programas necesitan repetidamente el elemento más urgente de una colección cambiante: el siguiente evento de una simulación, el nodo no visitado más cercano en el algoritmo de Dijkstra, la tarea de mayor prioridad o los k valores mayores de un flujo de datos. Ordenar toda la colección tras cada inserción cuesta O(n log n) cada vez. Una lista ordenada abarata la extracción pero la inserción es O(n). Un montículo hace que tanto insertar como extraer el mínimo cuesten O(log n), justo lo que necesita una cola de prioridad.

La idea: un árbol guardado en un arreglo

Un montículo es un árbol binario completo: todos los niveles están llenos salvo quizá el último, que se llena de izquierda a derecha. Esa forma permite guardar el árbol en una lista simple sin punteros.

Dos operaciones de reparación mantienen la propiedad del heap. Sift up: tras añadir un elemento nuevo al final, se intercambia con su padre mientras sea menor. Sift down: tras mover el último elemento a la raíz, se intercambia con su hijo menor mientras sea mayor que ese hijo. Cada operación recorre un único camino de la raíz a una hoja, así que hace como máximo unos log2(n) intercambios.

Ejemplo resuelto: push y pop

Parte del min-heap [2, 5, 3, 9, 6] (2 es la raíz, sus hijos son 5 y 3, y 5 tiene hijos 9 y 6).

1. Push de 1: añádelo al final, resulta [2, 5, 3, 9, 6, 1]. El índice 5 tiene como padre el índice 2 (valor 3).
2. 1 es menor que 3, intercambia: [2, 5, 1, 9, 6, 3]. Ahora el índice 2 tiene como padre el índice 0 (valor 2).
3. 1 es menor que 2, intercambia: [1, 5, 2, 9, 6, 3]. Llegó a la raíz, detente.
4. Pop: quita la raíz 1 y mueve el último elemento 3 a la raíz: [3, 5, 2, 9, 6].
5. Los hijos de la raíz son 5 y 2; el menor es 2, y 3 es mayor, intercambia: [2, 5, 3, 9, 6]. El índice 2 no tiene hijos, detente. El pop devolvió 1.

Implementación en Python de un min-heap

Esta clase muestra la mecánica. En código real usa heapq, que se ve en la siguiente sección.

class MinHeap:
    def __init__(self):
        self.a = []
    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i > 0 and a[i] < a[(i - 1) // 2]:      # sift up
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p
    def pop(self):
        a = self.a
        top, last = a[0], a.pop()                   # IndexError if empty
        if a:
            a[0], i = last, 0
            while True:                             # sift down
                c = 2 * i + 1
                if c + 1 < len(a) and a[c + 1] < a[c]:
                    c += 1                          # pick the smaller child
                if c >= len(a) or a[i] <= a[c]:
                    break
                a[i], a[c] = a[c], a[i]
                i = c
        return top
h = MinHeap()
for x in [5, 3, 9, 1, 6, 2]:
    h.push(x)
print([h.pop() for _ in range(6)])  # [1, 2, 3, 5, 6, 9]

Colas de prioridad con heapq de Python

El módulo heapq trabaja sobre una lista normal y la mantiene siempre como un min-heap. heapify convierte una lista existente en un montículo in situ en O(n). Para usar prioridades, apila tuplas: Python compara las tuplas elemento a elemento, así que el primer elemento es la prioridad. Añade un contador como desempate para que los elementos con igual prioridad nunca tengan que compararse directamente.

import heapq
from itertools import count
nums = [7, 2, 9, 4, 1]
heapq.heapify(nums)
print(nums[0], heapq.heappop(nums))      # 1 1
print(heapq.nlargest(2, [7, 2, 9, 4]))   # [9, 7]
tasks, order = [], count()
heapq.heappush(tasks, (2, next(order), "write report"))
heapq.heappush(tasks, (1, next(order), "fix outage"))
heapq.heappush(tasks, (2, next(order), "reply to email"))
while tasks:
    priority, _, name = heapq.heappop(tasks)
    print(priority, name)
# 1 fix outage
# 2 write report
# 2 reply to email

Para un max-heap, Python 3.14 añadió heapq.heapify_max, heapq.heappush_max y heapq.heappop_max. En versiones anteriores, el truco habitual es insertar claves negadas, por ejemplo heapq.heappush(h, -score), y negarlas de nuevo al extraer.

Complejidad temporal y espacial

Construir un montículo llamando a push n veces cuesta O(n log n). heapify hace sift down desde el último padre hasta la raíz y cuesta O(n), así que prefiérelo cuando ya tienes todos los elementos.

Variantes y errores comunes

• Max-heap: el mismo código con la comparación invertida; en Python, usa las funciones _max (3.14 y posteriores) o niega las claves.
• Heap d-ario: cada nodo tiene d hijos. Un árbol menos profundo abarata el push y encarece un poco el pop.
• Cola de prioridad indexada / decrease-key: heapq no puede cambiar in situ la prioridad de un elemento. Una solución habitual (usada en el algoritmo de Dijkstra) es insertar una entrada nueva y saltar las entradas obsoletas cuando se extraen.
• Comparar elementos no comparables: insertar (priority, dict) lanza TypeError cuando dos prioridades son iguales, porque Python pasa a comparar los diccionarios. Añade un contador como segundo elemento de la tupla.
• Tratar la lista del montículo como ordenada. Solo heap[0] está garantizado; usa sorted(heap) si necesitas todo en orden.
• Errores de desfase de uno al mezclar fórmulas con base 1 (hijos 2i y 2i + 1) de los libros de texto con listas de Python con base 0.

Cuándo usar un montículo y problemas típicos

Usa un montículo cuando necesites repetidamente solo el elemento menor o mayor de una colección que cambia. Usa una lista ordenada o un árbol balanceado cuando además necesites iteración ordenada o eliminaciones arbitrarias, y un simple min() cuando solo necesites el mínimo una vez.

Usos clásicos: camino más corto de Dijkstra y árbol de expansión mínima de Prim, mezclar k listas ordenadas (heapq.merge), hallar los k elementos mayores o menores (mantén un montículo de tamaño k, O(n log k)), la mediana móvil (dos montículos), planificadores de tareas y simulaciones dirigidas por eventos, y heapsort.