Heap es una estructura de datos basada en un árbol binario completo almacenado en un array, que satisface la heap property: en un min-heap, cada nodo es menor o igual que sus hijos; en un max-heap, cada nodo es mayor o igual que sus hijos.
Es la base para priority queues, heap sort, y Dijkstra’s algorithm.
Heap Property
Min-heap: parent.val <= child.val para todo nodo.
Max-heap: parent.val >= child.val para todo nodo.
El elemento mínimo/máximo siempre está en la raíz: peek en O(1).
Array Representation
Árbol binario completo almacenado en array:
- Hijo left de
i:2*i + 1 - Hijo right de
i:2*i + 2 - Padre de
i:(i-1) // 2
Min-heap: [1, 3, 2, 6, 5, 4]
Árbol:
1
/ \\
3 2
/ \\ /
6 5 4Operaciones
| Operación | Complejidad | Descripción |
|---|---|---|
| Peek | O(1) | Retorna root sin eliminar |
| Insert | O(log n) | Añade al final, bubble-up |
| Extract | O(log n) | Retorna root, reemplaza con último, bubble-down |
| Heapify | O(n) | Construye heap desde array |
Insert (Sift-up)
- Añade elemento al final del array.
- Compara con padre: si viola heap property, swap.
- Repite hasta llegar a raíz o cumplir property.
Extract (Sift-down)
- Retorna root (mínimo/máximo).
- Reemplaza root con último elemento.
- Compara con hijos: swap con el hijo más pequeño (min-heap) o más grande (max-heap).
- Repite hasta cumplir property.
Heapify
Construye heap desde array en O(n) procesando nodos desde el último internal node hasta la raíz.
Casos Extremos
- Array ya ordenado — heapify sigue siendo O(n), no O(n log n).
- Todos elementos iguales — heap property se cumple trivialmente.
- Insert y extract repetidos — amortizado O(log n) por operación.
- HeapSort — usa max-heap para ordenar in-place en O(n log n).
Comparación
| Estructura | Peek | Insert | Extract | Use case |
|---|---|---|---|---|
| Min-heap | O(1) | O(log n) | O(log n) | Dijkstra, scheduling |
| Max-heap | O(1) | O(log n) | O(log n) | HeapSort, priority queue |
| Binary Search Tree | O(log n)* | O(log n)* | O(log n)* | Range queries, sorted data |
*Solo si balanceado.
Aplicaciones
- Priority queue — scheduling, event simulation
- Dijkstra’s algorithm — extrae nodo con menor distancia
- HeapSort — ordenamiento in-place O(n log n)
- k-largest/k-smallest — mantiene heap de tamaño k
- Median maintenance — two heaps (min + max)
- Enseñanza — introduce priority queues y heap property
Trayectoria de Práctica
- Implementa min-heap con array; traza insert y extract.
- Implementa heapify; verifica que es O(n).
- Implementa HeapSort.
- Investiga Fibonacci heap: ¿cómo mejora a O(1) amortizado insert?
- Investiga pairing heap: ¿por qué es práctico?