Heap — Principios de la cola de prioridad

Al finalizar este tema

Podrás explicar la estructura y el funcionamiento del heap, e implementar una cola de prioridad con heapq de Python para resolver problemas de "extraer rápidamente el valor más pequeño (o más grande)".

Problema — Extraer rápidamente lo "más urgente"

Imagina la sala de emergencias de un hospital. El orden de tratamiento no depende del orden de llegada (cola), sino de la gravedad de los síntomas. ¿Cómo se podría implementar una "cola con prioridad"?

• Lista ordenada: ordenar cada vez que se inserta → O(n)
• Lista desordenada: búsqueda exhaustiva para encontrar el mínimo → O(n)

El heap procesa tanto la inserción como la extracción del valor mínimo en O(log n).

Reglas del heap

La regla de un min heap es sencilla:

El padre siempre es menor o igual que sus hijos

1          ← el valor mínimo está siempre en la raíz
       / \
      3   5
     / \ / \
    7  4 8  6

Dado que la raíz siempre contiene el valor más pequeño, se puede verificar el mínimo en O(1).

Diferencia con el BST: en un BST se mantiene la propiedad "izquierda < padre < derecha", pero en un heap solo se garantiza que "padre < hijos". El orden entre hermanos no importa.

Representación mediante arreglos

El heap es un árbol, pero en la práctica se almacena en un arreglo:

índice:  [0, 1, 2, 3, 4, 5, 6]
valor:   [1, 3, 5, 7, 4, 8, 6]

Para el índice del padre i:
  hijo izquierdo = 2*i + 1
  hijo derecho = 2*i + 2
  padre = (i - 1) // 2

Hijos del índice 0: 1, 2 / Hijos del índice 1: 3, 4 / Hijos del índice 2: 5, 6. La relación padre-hijo se puede determinar únicamente mediante el cálculo de índices, sin necesidad de punteros.

Principios de inserción y eliminación

Inserción (heappush): Se añade al final del arreglo y se desplaza hacia arriba comparándolo con su padre (sift up):

Inicial: [1, 3, 5, 7, 4, 8, 6]
Inserción de 2: [1, 3, 5, 7, 4, 8, 6, 2]
       ↑ padre del índice 7 (índice 3) = valor en índice 3 (valor 7)
       ↑ padre del índice 7 (índice 3) = valor en índice 3 (valor 7)
       ↑ padre del índice 3 = índice 1 (valor 3)
       2 < 3 → intercambio: [1, 2, 5, 3, 4, 8, 6, 7]
       ↑ padre del índice 1 = índice 0 (valor 1)
       2 > 1 → detener

Eliminar (heappop): Elimina la raíz y coloca el último elemento en su lugar, desplazándolo hacia abajo (sift down) tras compararlo con sus hijos. Ambas operaciones requieren solo un desplazamiento proporcional a la altura del árbol, por lo que su complejidad es O(log n).

heapq de Python

Python proporciona un montículo mínimo mediante el módulo heapq:

import heapq

# Usar una lista vacía como heap
heap = []

# Inserción — O(log n)
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)

print(heap)        # [1, 3, 7, 5] — el orden interno sigue las reglas del heap
print(heap[0])     # 1 — el valor mínimo está siempre en el índice 0

# Extracción del valor mínimo — O(log n)
smallest = heapq.heappop(heap)
print(smallest)    # 1
print(heap)        # [3, 5, 7]

Solo necesitas recordar heappush y heappop.

Convertir una lista existente en un heap

data = [9, 1, 4, 7, 2, 8, 3]
heapq.heapify(data)  # O(n) — más rápido que ordenar (O(n log n))
print(data)          # [1, 2, 3, 7, 9, 8, 4]

heapify convierte una lista en un heap in-place.

Implementación de la cola de prioridad

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def push(self, priority, item):
        heapq.heappush(self.heap, (priority, item))

    def pop(self):
        return heapq.heappop(self.heap)[1]

    def is_empty(self):
        return len(self.heap) == 0

# Ejemplo de sala de emergencias
er = PriorityQueue()
er.push(3, "paciente con resfriado")
er.push(1, "paciente en paro cardíaco")    # prioridad 1 es la más urgente
er.push(2, "paciente con fractura")

print(er.pop())  # "paciente con fractura"
print(er.pop())  # "paciente con resfriado"
print(er.pop())  # "paciente en paro cardíaco"

El primer elemento de la tupla se utiliza como criterio de comparación. Cuanto menor sea el número, mayor será su prioridad.

Cuando se necesita un max-heap

Python heapq solo proporciona un min-heap. Si necesitas un max-heap, ingresa los valores como negativos:

# Efecto de máximo heap
max_heap = []
for val in [3, 1, 5, 2, 4]:
    heapq.heappush(max_heap, -val)

print(-heapq.heappop(max_heap))  # 5 (el valor más grande)
print(-heapq.heappop(max_heap))  # 4

Funciones útiles

data = [7, 3, 9, 1, 5, 8, 2]

# Los 3 más pequeños
print(heapq.nsmallest(3, data))  # [1, 2, 3]

# Los 3 más grandes
print(heapq.nlargest(3, data))   # [9, 8, 7]

# Fusionar varias listas ordenadas en una
a = [1, 4, 7]
b = [2, 5, 8]
c = [3, 6, 9]
print(list(heapq.merge(a, b, c)))  # [1, 2, 3, 4, 5, 6, 7, 8, 9]

Resumen de la complejidad temporal

Ordenamiento por heap

Se puede realizar el ordenamiento utilizando un heap:

def heap_sort(arr):
    heapq.heapify(arr)  # O(n)
    return [heapq.heappop(arr) for _ in range(len(arr))]

data = [7, 3, 9, 1, 5]
print(heap_sort(data))  # [1, 3, 5, 7, 9]

La complejidad temporal es O(n log n), equivalente a la de Quicksort y Mergesort. En la práctica, sorted()(Timsort) de Python es más rápido; sin embargo, es importante comprender conceptualmente el principio de Heapsort.

Aplicación práctica — Problema Top K

El problema de encontrar "los 10 elementos más grandes entre 1 millón de datos":

import heapq

data = [random.randint(0, 1_000_000) for _ in range(1_000_000)]

# ❌ Ordenamiento completo — O(n log n)
top10_sort = sorted(data, reverse=True)[:10]

# ✅ Uso de heap — O(n log k)
top10_heap = heapq.nlargest(10, data)

Ordenar todo requiere O(n log n), pero como el heap solo mantiene un tamaño de k, la complejidad es O(n log k). La diferencia es significativa cuando k es mucho menor que n.

# La implementación directa muestra el principio
min_heap = []
for val in data:
    if len(min_heap) < 10:
        heapq.heappush(min_heap, val)
    elif val > min_heap[0]:
        heapq.heapreplace(min_heap, val)

top10 = sorted(min_heap, reverse=True)

Se mantiene un min-heap de tamaño 10. Si un nuevo valor es mayor que el mínimo del heap, se reemplaza. Al final, los 10 valores restantes son los 10 más grandes de todo el conjunto.

En la práctica — Algoritmo de Dijkstra

El algoritmo de Dijkstra, para encontrar el camino más corto, también utiliza un heap:

def dijkstra(graph, start):
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        cost, node = heapq.heappop(heap)
        if cost > dist[node]:
            continue
        for neighbor, weight in graph[node]:
            new_cost = cost + weight
            if new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                heapq.heappush(heap, (new_cost, neighbor))
    return dist

Como se debe extraer en cada paso el nodo más cercano entre los que aún no han sido visitados, la complejidad es O(V²) sin un montículo (heap) y O((V+E) log V) al utilizarlo.

Un montículo (heap) es óptimo para situaciones donde no es necesario ordenar todo el conjunto, sino solo extraer rápidamente el elemento más importante.