← Estructuras de datos desde cero · Lección 22/32
Un árbol guardado en un arreglo
El más chico, siempre arriba
Un montículo mínimo (*min-heap*) es un árbol binario con dos reglas:
- Cada padre es menor o igual que sus hijos. Por eso la raíz es el mínimo de todo.
- Es completo: se llena por niveles, de izquierda a derecha, sin huecos.
No está ordenado del todo: entre hermanos o primos no hay ninguna regla. Sólo promete una cosa, que el más chico está arriba, y eso es justo lo que lo hace barato.
Como no tiene huecos, no necesita nodos ni punteros: se guarda en un arreglo, nivel por nivel. Los hijos de la posición i están en 2i + 1 y 2i + 2, y su padre en (i - 1) >> 1 (dividir entre 2 y quitar decimales).
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
- Cada padre es menor que sus dos hijos: 1 → 3 y 2; 3 → 7 y 4; 2 → 5 y 8.
- La posición 5 (el 5) tiene de padre a la 2 (el 2).
- El mínimo está en
heap[0]: leerlo cuesta O(1).
Toda la lección en una página
El más chico, siempre arriba
Un montículo mínimo (*min-heap*) es un árbol binario con dos reglas:
- Cada padre es menor o igual que sus hijos. Por eso la raíz es el mínimo de todo.
- Es completo: se llena por niveles, de izquierda a derecha, sin huecos.
No está ordenado del todo: entre hermanos o primos no hay ninguna regla. Sólo promete una cosa, que el más chico está arriba, y eso es justo lo que lo hace barato.
Como no tiene huecos, no necesita nodos ni punteros: se guarda en un arreglo, nivel por nivel. Los hijos de la posición i están en 2i + 1 y 2i + 2, y su padre en (i - 1) >> 1 (dividir entre 2 y quitar decimales).
// El árbol del dibujo, guardado por niveles
const heap = [1, 3, 2, 7, 4, 5, 8];
for (let i = 0; i < heap.length; i++) {
const izq = 2 * i + 1, der = 2 * i + 2;
if (izq < heap.length) {
console.log("posición", i, "valor", heap[i], "-> hijos", heap[izq], heap[der]);
}
}
console.log("el padre de la posición 5 es", heap[(5 - 1) >> 1]);
console.log("el mínimo:", heap[0]);
- Cada padre es menor que sus dos hijos: 1 → 3 y 2; 3 → 7 y 4; 2 → 5 y 8.
- La posición 5 (el 5) tiene de padre a la 2 (el 2).
- El mínimo está en
heap[0]: leerlo cuesta O(1).
Meter: al final, y subir
Para meter un valor sin romper la forma, va al final del arreglo (el siguiente hueco del último nivel). Luego sube: mientras sea menor que su padre, se intercambian.
Como el árbol es completo, su altura es log₂ n, y subir da a lo más esa cantidad de pasos: O(log n). Mira cómo queda el arreglo después de cada valor.
function subir(heap, i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p] <= heap[i]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
}
function meter(heap, valor) {
heap.push(valor);
subir(heap, heap.length - 1);
}
const heap = [];
for (const v of [5, 3, 8, 1, 9, 2]) {
meter(heap, v);
console.log(v, "->", heap);
}
- Al meter el 1 entra al final,
[3, 5, 8, 1], y sube dos veces: pasa al 5 y luego al 3, hasta quedar en la raíz. - El 9 no sube nada: ya es mayor que su padre.
- El 2 sube una vez y se queda bajo el 1. El arreglo final no está ordenado, pero el mínimo está en la posición 0.
Sacar el mínimo: el último arriba, y bajar
El mínimo es la raíz. Para quitarla sin dejar hueco, el último elemento pasa a la raíz y baja: se intercambia con el menor de sus dos hijos mientras alguno sea menor que él. También es O(log n).
Si sacas el mínimo una y otra vez, los valores salen en orden: eso es heapsort, ordenar en O(n log n) sin memoria extra.
function bajar(heap, i) {
const n = heap.length;
while (true) {
const izq = 2 * i + 1, der = 2 * i + 2;
let menor = i;
if (izq < n && heap[izq] < heap[menor]) menor = izq;
if (der < n && heap[der] < heap[menor]) menor = der;
if (menor === i) break;
[heap[menor], heap[i]] = [heap[i], heap[menor]];
i = menor;
}
}
function sacar(heap) {
const min = heap[0];
const ultimo = heap.pop();
if (heap.length > 0) {
heap[0] = ultimo;
bajar(heap, 0);
}
return min;
}
const heap = [1, 3, 2, 5, 9, 8];
console.log(sacar(heap), heap);
const salen = [];
while (heap.length > 0) salen.push(sacar(heap));
console.log(salen);
- Al sacar el 1, el 8 (el último) pasa a la raíz y baja hasta su lugar: queda
[2, 3, 8, 5, 9]. - Sacando todo, sale
[2, 3, 5, 8, 9]: ordenado. - El
ifcuida el caso de un solo elemento: sin él, el último volvería a entrar después de sacarlo.