1. ¿Qué es un Heap?

Un heap es una estructura de datos basada en un árbol binario completo que satisface la propiedad de heap:

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

Gracias a su forma completa, los heaps permiten acceso O(1) al elemento de mayor (o menor) prioridad y inserciones y extracciones en O(log n).

2. Tipos de Heap y Comparativas

3. Implementación con heapq (Python estándar)

El módulo heapq de la biblioteca estándar provee un min‑heap basado en listas. No hay una clase separada; la lista misma actúa como heap.

3.1 Operaciones básicas

import heapq
# Creación de un heap vacío
heap = []
# Insertar elementos (push)
for valor in [7, 2, 5, 1, 9]:
    heapq.heappush(heap, valor)
print('Heap interno:', heap)   # [1, 2, 5, 7, 9]
# Obtener el menor sin remover (peek)
menor = heap[0]
print('Menor (peek):', menor)
# Extraer el menor (pop)
while heap:
    print('Extraído:', heapq.heappop(heap))

3.2 Convertir una lista en heap (heapify)

import heapq
lista = [20, 5, 15, 22, 9]
heapq.heapify(lista)   # transforma la lista en heap in‑place
print('Heapify resultante:', lista)

3.3 Max‑Heap con heapq

Python no tiene un max‑heap nativo, pero se puede simular invirtiendo el signo de los valores.

import heapq
valores = [3, 1, 4, 1, 5]
max_heap = [-v for v in valores]
heapq.heapify(max_heap)
print('Máximo:', -heapq.heappop(max_heap))   # 5

4. Clase personalizada: BinaryHeap (soporta min y max)

Para proyectos que requieran una API orientada a objetos o la capacidad de alternar entre min‑ y max‑heap sin cambiar los datos, podemos crear una envoltura ligera.

class BinaryHeap:
    """Heap binario configurable como min‑heap (default) o max‑heap.
    Args:
        iterable (iterable, optional): Valores iniciales.
        mode (str): 'min' o 'max'.
    """
    def __init__(self, iterable=None, mode='min'):
        self._min = mode == 'min'
        self._data = []
        if iterable:
            self._data = list(iterable)
            self._heapify()
    def _transform(self, value):
        # Invertimos el signo si es max‑heap para reutilizar heapq internamente
        return value if self._min else -value
    def _inverse(self, value):
        return value if self._min else -value
    def _heapify(self):
        self._data = [self._transform(v) for v in self._data]
        import heapq
        heapq.heapify(self._data)
    def push(self, value):
        import heapq
        heapq.heappush(self._data, self._transform(value))
    def pop(self):
        import heapq
        return self._inverse(heapq.heappop(self._data))
    def peek(self):
        return self._inverse(self._data[0]) if self._data else None
    def __len__(self):
        return len(self._data)
    def __repr__(self):
        return f"BinaryHeap({[self._inverse(v) for v in self._data]}, mode={'min' if self._min else 'max'})"
# Uso práctico
min_h = BinaryHeap([8, 3, 5], mode='min')
min_h.push(2)
print('Min‑heap peek ->', min_h.peek())   # 2
print('Pop ->', min_h.pop())             # 2
max_h = BinaryHeap([8, 3, 5], mode='max')
max_h.push(10)
print('Max‑heap peek ->', max_h.peek())   # 10
print('Pop ->', max_h.pop())             # 10

Esta clase encapsula la lógica de inversión de signo, brinda push, pop, peek y una representación legible. Es útil en proyectos donde la claridad del API supera la micro‑optimización.

5. Casos de Uso Reales

• Colas de prioridad en sistemas de mensajería: procesar los mensajes más urgentes primero.
• Algoritmos de grafos: Dijkstra y Prim usan heaps para seleccionar la arista/costo mínimo.
• Streaming de datos: mantener los k mayores o menores valores en tiempo real.
• Programación de tareas (scheduler): ejecutar la tarea con la fecha más próxima.

6. Optimización y Buenas Prácticas

6.1 Evitar conversiones innecesarias

Cuando se trabaja con heapq, mantenga la lista como heap en todo momento; evitar list.sort() entre operaciones.

6.2 Pre‑asignar capacidad

Si conoce el número aproximado de elementos, utilice list.extend([None]*n) y luego heapify para reducir el número de realocaciones.

6.3 Operaciones de decrease‑key

Python heapq no soporta decrease‑key nativamente. La estrategia típica es marcar el nodo antiguo como invalidado y volver a insertarlo con la nueva prioridad.

import heapq
heap = []
entry_finder = {}
REMOVED = ''
def add_task(task, priority=0):
    if task in entry_finder:
        remove_task(task)
    entry = [priority, task]
    entry_finder[task] = entry
    heapq.heappush(heap, entry)
def remove_task(task):
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED
def pop_task():
    while heap:
        priority, task = heapq.heappop(heap)
        if task is not REMOVED:
            del entry_finder[task]
            return task, priority
    raise KeyError('pop from an empty priority queue')

6.4 Seguridad y Validación de Entrada

En entornos multi‑tenant, valide que los objetos insertados en el heap implementen comparadores consistentes (__lt__); de lo contrario, heapq lanzará TypeError.

7. Compatibilidad, Rendimiento y Escalabilidad

El módulo heapq está disponible desde Python 2.3 y sigue sin cambios en la API hasta Python 3.12, por lo que el código es compatible con todas las versiones modernas de Python. En términos de rendimiento:

• Operación heappush/heappop: ~0.5 µs por elemento en CPython 3.12 (CPU Intel i7).
• Para millones de elementos, la sobrecarga de Python puede ser significativa; considere pyskiplist o heaptrack si la latencia es crítica.

Si la aplicación necesita concurrencia, utilice queue.PriorityQueue (basado en heapq) con bloqueos internos o emplee Redis Sorted Sets como heap distribuido.

8. Solución de Problemas (Troubleshooting)

8.1 "TypeError: '

Ocurre cuando los objetos inseridos no son comparables. Solución: implemente __lt__ o use una tupla (priority, contador, objeto) donde contador garantiza unicidad.

8.2 Heap desbalanceado tras múltiples pop y push

El heap siempre mantiene la propiedad tras cada operación; sin embargo, si manipula la lista directamente (p.ej., list.append()) sin heappush, la estructura se corrompe. Re‑ejecute heapify() para restaurarla.

8.3 Consumo elevado de memoria

Los heaps almacenan todos los elementos en memoria. Para flujos de datos gigantes, utilice heaps externos (algoritmo de selección parcial) o procesos por lotes que mantengan solo k elementos en el heap.

9. Resumen y Próximos Pasos

Los heaps son una herramienta fundamental para cualquier ingeniero de software que necesite gestión de prioridades eficiente. Con heapq y una capa de abstracción propia, puede cubrir desde simples colas de trabajo hasta algoritmos de grafos de gran escala.

Para seguir profundizando:

1. Explorar la documentación oficial y testear con timeit.
2. Implementar un Fibonacci Heap en Cython para casos de uso de decrease‑key intensivo.
3. Integrar heapq con asyncio para colas de prioridad asíncronas.

¡Domina los heaps y lleva tus aplicaciones a un nuevo nivel de rendimiento y escalabilidad!