Heaps y Colas de Prioridad
¿Qué es un montón?
Un montón es un árbol binario completo donde cada padre satisface la propiedad del montón, ya sea siempre más pequeño (montón mínimo) o siempre más grande (montón máximo) que sus hijos. "Completo" significa que todos los niveles están llenos excepto posiblemente el último, que se llena de izquierda a derecha.
1 Min-heap
/ \
3 5
/ \
7 4
Como está completo, lo almacenamos en una matriz plana; no se necesitan punteros. Para el índice i: hijo izquierdo = 2i + 1, hijo derecho = 2i + 2, padre = (i - 1) // 2.
Montón mínimo frente a montón máximo
| Propiedad | Montón mínimo | Montón máximo | |----------|----------|----------| | Raíz | Elemento más pequeño | Elemento más grande | | ¿Padre ≤ hijos? | ✅ Sí | ❌ No (≥) | | Extracto da | Mínimo | Máximo |
El heapq de Python es un montón mínimo de forma predeterminada. Para un montón máximo, niegue los valores al insertar y niegue nuevamente al extraer.
Insertar y extraer: paso a paso
Insertar: presione hasta el final, luego haga burbujas (intercambie con el padre cuando sea más pequeño):
import heapq
h = [1, 3, 5, 7]
heapq.heappush(h, 2) # h becomes [1, 2, 5, 7, 3]
Extraer mínimo: intercambie la raíz con el último elemento, haga estallar el último, luego tamice hacia abajo (intercambie con un elemento más pequeño):
smallest = heapq.heappop(h) # returns 1
Ambas operaciones se ejecutan en O(log n) porque la altura del árbol es log n.
Discusión
Iniciar sesión unirse a la discusión