¿Qué es un heap y cómo implementa una cola de prioridad?

Question

Accepted Answer

Un **heap binario** es un árbol binario completo almacenado en un array que mantiene la **propiedad de heap**: en un **min-heap**, cada padre es ≤ que sus hijos, por lo que el **mínimo siempre está en la raíz**. Esto lo convierte en la **implementación estándar de una cola de prioridad**.

## Distribución en array

```text
       1               index: 0  1  2  3  4
      / \              array: [1, 3, 5, 8, 4]
     3   5             parent(i) = (i-1)//2
    / \                left(i)   = 2i+1
   8   4               right(i)  = 2i+2
```

## Operaciones

```python
import heapq
h = []
heapq.heappush(h, 5)   # O(log n) — bubble up
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0]        # peek min -> O(1)
heapq.heappop(h)       # O(log n) — remove root, sift down -> 1
```

## Complejidad

| Operación | Tiempo |
|---|---|
| peek mín/máx | O(1) |
| push (insertar) | O(log n) |
| pop (extraer) | O(log n) |
| construir heap desde n elementos | O(n) |

## Cuándo usarlo

- **Planificación** por prioridad (p. ej. planificadores de tareas del SO).
- **Algoritmos Dijkstra / Prim** para camino más corto y MST.
- **Problemas Top-K** y medianas en streaming.
- **Heap sort** (in-place O(n log n)).

## Por qué es importante

Un heap te da el elemento más importante siguiente al instante sin necesidad de mantener todo completamente ordenado, lo que es mucho más barato que volver a ordenar.

Es la columna vertebral de algoritmos impulsados por prioridad y una herramienta frecuente en entrevistas para preguntas de "k más grandes/pequeños".

Operación	Tiempo
peek mín/máx	O(1)
push (insertar)	O(log n)
pop (extraer)	O(log n)
construir heap desde n elementos	O(n)