1. ¿Qué es un árbol de prioridad?

Un árbol de prioridad, también conocido como heap, es una estructura de datos basada en un árbol binario completo que mantiene la propiedad de heap:

• Max‑Heap: el valor de cada nodo es mayor o igual que el de sus hijos.
• Min‑Heap: el valor de cada nodo es menor o igual que el de sus hijos.

Esta característica permite que la operación de obtener el elemento de mayor (o menor) prioridad se realice en tiempo O(1), mientras que inserciones y eliminación del nodo raíz se ejecutan en O(log n).

2. Tipos de árboles de prioridad y cuándo usarlos

Existen varias variantes de heaps, cada una optimizada para diferentes patrones de uso:

En Python, el heapq estándar implementa un binary min‑heap usando una lista. En la mayoría de los casos es suficiente y extremadamente rápido.

3. Implementación manual de un Binary Max‑Heap

A continuación, una clase completa que gestiona un max‑heap sin depender de librerías externas.

class MaxHeap:
    """Binary Max‑Heap implementado con una lista.
    Operaciones principales:
      - insert(item): O(log n)
      - extract_max(): O(log n)
      - peek(): O(1)
    """
    def __init__(self):
        self._data = []  # lista 0‑indexada
    # ---------- Utilidades internas ----------
    def _parent(self, idx):
        return (idx - 1) // 2 if idx > 0 else None
    def _left(self, idx):
        left = 2 * idx + 1
        return left if left < len(self._data) else None
    def _right(self, idx):
        right = 2 * idx + 2
        return right if right < len(self._data) else None
    def _swap(self, i, j):
        self._data[i], self._data[j] = self._data[j], self._data[i]
    # ---------- Operaciones públicas ----------
    def insert(self, item):
        """Añade un nuevo elemento manteniendo la propiedad de max‑heap."""
        self._data.append(item)
        self._sift_up(len(self._data) - 1)
    def _sift_up(self, idx):
        while idx > 0:
            parent = self._parent(idx)
            if self._data[parent] < self._data[idx]:
                self._swap(parent, idx)
                idx = parent
            else:
                break
    def peek(self):
        """Devuelve el elemento máximo sin eliminarlo."""
        if not self._data:
            raise IndexError("peek from an empty heap")
        return self._data[0]
    def extract_max(self):
        """Elimina y devuelve el máximo (raíz)."""
        if not self._data:
            raise IndexError("extract from an empty heap")
        max_item = self._data[0]
        # Mover el último elemento a la raíz y re‑heapificar
        last = self._data.pop()
        if self._data:
            self._data[0] = last
            self._sift_down(0)
        return max_item
    def _sift_down(self, idx):
        size = len(self._data)
        while True:
            left = self._left(idx)
            right = self._right(idx)
            largest = idx
            if left is not None and self._data[left] > self._data[largest]:
                largest = left
            if right is not None and self._data[right] > self._data[largest]:
                largest = right
            if largest != idx:
                self._swap(idx, largest)
                idx = largest
            else:
                break
    def __len__(self):
        return len(self._data)
    def __repr__(self):
        return f"MaxHeap({self._data})"

Ejemplo de uso:

if __name__ == "__main__":
    heap = MaxHeap()
    for value in [15, 3, 17, 10, 84, 19, 6, 22, 9]:
        heap.insert(value)
    print("Heap interno:", heap)
    print("Máximo actual:", heap.peek())
    while len(heap):
        print("Extracted:", heap.extract_max())

Salida esperada:

Heap interno: MaxHeap([84, 22, 19, 15, 10, 17, 6, 3, 9])
Máximo actual: 84
Extracted: 84
Extracted: 22
Extracted: 19
Extracted: 17
Extracted: 15
Extracted: 10
Extracted: 9
Extracted: 6
Extracted: 3

4. Usando la librería estándar heapq (Min‑Heap)

Python incluye heapq, una implementación ligera y optimizada de un min‑heap. Para obtener un max‑heap basta con invertir la clave (p. ej. usando valores negativos o functools.total_ordering).

4.1 Operaciones básicas

import heapq
# Crear una cola de prioridad vacía
pq = []
# Insertar elementos (valor, payload)
heapq.heappush(pq, (5, "tarea A"))
heapq.heappush(pq, (1, "tarea B"))
heapq.heappush(pq, (3, "tarea C"))
# Ver el elemento de mayor prioridad (menor valor numérico)
print("Siguiente tarea:", pq[0])
# Extraer en orden de prioridad
while pq:
    priority, task = heapq.heappop(pq)
    print(f"Ejecutando {task} con prioridad {priority}")

4.2 Max‑Heap mediante valores negativos

import heapq
max_pq = []
for priority, item in [(10, "A"), (5, "B"), (20, "C")]:
    heapq.heappush(max_pq, (-priority, item))
while max_pq:
    prio, it = heapq.heappop(max_pq)
    print(f"Item {it} con prioridad {-prio}")

Esta técnica es suficiente para la mayoría de los casos y evita la sobrecarga de una clase personalizada.

5. Comparativa: Heap vs. Otras estructuras de cola de prioridad

• Lista ordenada: inserción O(n), extracción O(1). No escalable para inserciones frecuentes.
• Árbol balanceado (e.g., bisect + lista): inserción O(log n), extracción O(log n), mayor overhead de memoria.
• Heap (binary): inserción y extracción O(log n), constante extra para peek. Mejor relación tiempo‑memoria para la mayoría de los algoritmos de grafos.

En términos de rendimiento puro, heapq supera a bisect y a una lista ordenada en pruebas de inserción masiva (>10⁶ elementos).

6. Buenas prácticas y trucos avanzados

6.1 Evitar problemas con objetos mutables

Si insertas objetos que pueden cambiar su valor de prioridad después de estar en el heap, el orden quedará corrupto. La solución típica es:

• Usar tuplas inmutables ((priority, id, payload)) donde id garantiza unicidad.
• Al cambiar la prioridad, marcar el elemento como obsoleto y volver a insertarlo con la nueva prioridad.

6.2 Implementar decrease_key eficiente

Los heaps binarios no soportan decrease_key directamente. Una estrategia común es mantener un diccionario de índices para acceder al nodo y aplicar _sift_up manualmente. En entornos críticos, evalúa un Fibonacci Heap (disponible en paquetes como fibheap).

6.3 Uso de heapq.merge para combinar colas

import heapq
sorted1 = [1, 4, 7]
sorted2 = [2, 3, 6]
merged = list(heapq.merge(sorted1, sorted2))  # O(n)
print(merged)  # [1, 2, 3, 4, 6, 7]

Ideal cuando ya tienes varias listas previamente heapificadas y deseas iterar sin crear una nueva estructura.

7. Troubleshooting frecuente

• IndexError al hacer peek o extract_max: la heap está vacía. Verifica if heap: antes de operar.
• Orden incorrecto después de modificar un elemento: los heaps no se actualizan automáticamente. Re‑inserta el elemento o usa una estructura que soporte decrease_key.
• Rendimiento bajo con millones de elementos: usa heapq.heapify(list) para crear el heap en O(n) en vez de insertar uno a uno (cada inserción es O(log n)).

Ejemplo de heapify:

import heapq, random
data = random.sample(range(1_000_000), 500_000)
heapq.heapify(data)  # O(n)
print("Heap creado en", len(data), "elementos")

8. Compatibilidad, rendimiento y escalabilidad

La implementación de heapq está escrita en C (parte del intérprete CPython) y funciona con cualquier versión de Python ≥ 3.6. En PyPy, el rendimiento es comparable y a veces superior gracias al JIT.

8.1 Benchmarks rápidos (Python 3.11)

import time, heapq, random
N = 1_000_000
values = [random.randint(1, 10_000) for _ in range(N)]
# 1) Insertar uno a uno
start = time.perf_counter()
heap = []
for v in values:
    heapq.heappush(heap, v)
print('push O(log n):', time.perf_counter() - start)
# 2) heapify (O(n))
start = time.perf_counter()
heap = list(values)
heapq.heapify(heap)
print('heapify O(n):', time.perf_counter() - start)

En la mayoría de los servidores modernos, heapify de 1 M de elementos tarda ~0.05 s, mientras que insertar individualmente supera 0.7 s.

8.2 Escalado horizontal

Para sistemas distribuidos (p. ej., procesamiento de eventos en tiempo real), se suele combinar heapq con particionado por clave y colas de mensajes (Kafka, RabbitMQ). Cada partición mantiene su propio heap local, garantizando O(log n) por nodo y evitando cuellos de botella centralizados.

9. Conclusiones

Los árboles de prioridad (heaps) siguen siendo la herramienta predilecta para gestionar colas de prioridad eficientes. Python brinda dos caminos:

1. Uso directo de heapq para casos simples y máxima velocidad.
2. Implementaciones personalizadas (max‑heap, índices, decrease‑key) cuando se necesita un comportamiento especializado.

Aplicar buenas prácticas – evitar mutabilidad, usar heapify para cargas masivas y combinar con particionado – garantiza que tu solución escale sin sorpresas.