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.
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
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
| 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) |
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".
Una biblioteca de preguntas de entrevista de IT con respuestas detalladas — de Junior a Senior.
Donar