Data Structures
Lecciones · #7 de 11

Montículos y Colas de Prioridad

Respaldado por arreglo, mínimo en tiempo logarítmico — el motor de las colas de prioridad

Min-heap · array view ↔ tree view

array 
init

Pruébalo: Inserta y observa cómo parpadean los intercambios de pares en la subida (bubble-up). Luego extractMin — el hundimiento (sift-down) restaura el invariante. Mismo arreglo, dos formas de verlo: fila de celdas y árbol binario completo.

Por qué importa

Un montículo es el mismo árbol respaldado por arreglo de la lección de árboles binarios — pero con una regla extra que lo convierte en un motor de mínimo/máximo en tiempo constante. Cuando necesitas el elemento máximo (o mínimo) de forma rápida y repetida, los montículos son la respuesta. Impulsan las colas de prioridad, el ordenamiento por montículo (heap sort) y algoritmos como el camino más corto de Dijkstra (que viste en el modo de camino más corto de la lección de grafos).

El invariante del montículo

Dos invariantes, ambos deben cumplirse:

Invariantes del montículo
Forma: el árbol binario es completo — cada nivel está lleno excepto, posiblemente, el último, que se llena de izquierda a derecha. Esto nos permite almacenar el árbol de forma contigua en un arreglo, sin huecos.
Orden (montículo de mínimos): para cada nodo n, n.key ≤ key(child) para cada hijo. (Cambia a ≥ para un montículo de máximos.) Por lo tanto, la raíz contiene el mínimo (o el máximo).
Qué significa "preservar"
Insertar viola el orden temporalmente en la hoja, y luego la subida (bubble-up) lo restaura. Extraer viola ambos temporalmente (la última hoja se mueve a la raíz), y luego el hundimiento (sift-down) restaura el orden manteniendo la forma completa.

La idea

Imagina un cuadro de torneo donde el ganador siempre asciende a la cima. Después de cada partido, el mejor equipo sube.

Un montículo es así. En un montículo de máximos, cada padre es mayor que sus hijos. La raíz es siempre el máximo.

El truco ingenioso: ¡almacenarlo en un arreglo! Para el nodo en el índice i:

Insertar: Agregar al final, luego "subir" — intercambiar con el padre mientras sea mayor. Extraer el máximo: Quitar la raíz, poner el último elemento en la raíz, luego "hundir" — intercambiar con el hijo mayor mientras sea menor.

Ambas operaciones son O(log n) — apenas la altura del árbol.

Puntos clave

Profundizando

Montículo de mínimos vs montículo de máximos

Un montículo de mínimos pone el elemento más pequeño en la raíz; uno de máximos pone el más grande. El mecanismo es idéntico — solo se invierte la dirección de la comparación. Algunos lenguajes tienen un valor predeterminado en un sentido (la std::priority_queue de C++ es de máximos; heapq de Python es de mínimos) y niegas los valores para invertirlo — heapq.heappush(q, -value). Verifícalo siempre.

La prueba del heapify en O(n)

Pensarías que construir un montículo a partir de n elementos desordenados cuesta O(n log n) — una inserción O(log n) por elemento. Pero hay una forma mejor: copia el arreglo, luego hunde desde el índice del medio hacia la raíz. El costo total es O(n), no O(n log n).

La prueba es una hermosa suma geométrica. Un árbol binario completo de n nodos tiene aproximadamente n/2 hojas (profundidad 0 — sin necesidad de hundir), n/4 en la profundidad 1 (a lo sumo 1 intercambio cada una), n/8 en la profundidad 2 (a lo sumo 2 intercambios), …, 1 raíz en la profundidad log n (a lo sumo log n intercambios). El trabajo total:

trabajo ≤ Σ (n / 2^(d+1)) · d   para d = 0..log n
        = (n/2) · Σ d / 2^d
        ≤ (n/2) · 2     ya que Σ d/2^d converge a 2
        = O(n)

La mayoría de los nodos están cerca del fondo y se hunden cero o un nivel. Solo una fracción ínfima cerca de la cima hace el trabajo completo de log n. Este es otro sabor del análisis amortizado — el peor caso se concentra en unos pocos nodos, y son tan pocos que no llegan a dominar.

Montículo vs ABB — cuándo elegir cuál

Ambos te dan operaciones O(log n). Dos diferencias prácticas deciden cuál usar:

| Caso de uso | Montículo | ABB | |---|---|---| | Extracción repetida de mín/máx | ✓ peek O(1), pop O(log n) | también O(log n) para mín/máx | | Consultas por rango (encontrar todos > 50) | ✗ sin orden | ✓ O(log n + k) | | Recorrido inorden | ✗ | ✓ | | Sobrecarga de memoria | arreglo — sin punteros | 2 punteros + valor por nodo | | Factor constante | pequeño (arreglo, amigable con la caché) | mayor (persecución de punteros) | | Construir a partir de n elementos | heapify O(n) | inserción repetida O(n log n) |

Elige un montículo cuando solo necesitas mín/máx y nunca necesitas orden ni consultas por rango. Elige un ABB (normalmente balanceado) cuando necesitas iteración ordenada o "encontrar todas las claves en [a, b]". El modo de Dijkstra de la lección de grafos usa un montículo porque siempre necesita el nodo de la frontera más barato siguiente, no el orden de todos los nodos de la frontera.

El ordenamiento por montículo usa esto: heapify en O(n), luego extraer el máximo n veces para un O(n log n) total — pero con peor comportamiento de caché que el merge sort, así que rara vez es el ganador práctico a pesar de la asíntota coincidente.

Detalles matemáticos

Complejidad temporal
Insert: O(log n)
Extract max/min: O(log n)
Peek: O(1)
Heapify (build): O(n)
Fórmulas de índice del arreglo
left(i) = 2i + 1
right(i) = 2i + 2
parent(i) = lfloor(i-1)/2rfloor

Implementación

Operaciones del montículo

use std::collections::BinaryHeap;

let mut heap = BinaryHeap::new();
heap.push(3);
heap.push(1);
heap.push(4);  // Montículo: máximo en la cima

let max = heap.pop();  // Devuelve Some(4)
let peek = heap.peek(); // Devuelve Some(&3)

Cuándo usarlo

Práctica

Tres problemas que muestran por qué el montículo es tu herramienta por defecto para "dame las k mejores/peores cosas":

→ Explora todos los problemas de práctica