Data Structure & Algorithms
Heaps y priority queues
Heaps binarios y priority queues: representación en array, sift up y down, heapify, comparadores, top K y costos de prioridad dinámica.
- Última actualización
- Actualizada
- Nivel
- Aplicación
Data Structure & Algorithms
Heaps binarios y priority queues: representación en array, sift up y down, heapify, comparadores, top K y costos de prioridad dinámica.
Un heap mantiene el elemento con mayor prioridad en la raíz. No ordena todos los valores: solo conserva una relación entre cada padre y sus hijos.
3
/ \
5 8
/ \ /
10 7 12Este min-heap garantiza que 3 es el mínimo. No garantiza que 5 < 8, ni que un recorrido produzca los valores ordenados.
| Propiedad | Heap | Binary Search Tree |
|---|---|---|
| Orden | Padre frente a hijos | Subárbol izquierdo frente a nodo frente a derecho |
| Mínimo o máximo | O(1) en la raíz adecuada | O(h) siguiendo un extremo |
| Buscar un valor cualquiera | O(n) | O(h) |
| Representación habitual | Array | Nodos enlazados |
| Forma | Árbol binario completo | Puede tener distintas formas |
Un heap es útil para prioridades. Un BST es útil para mantener orden total y hacer búsquedas por clave.
Todos los niveles están llenos salvo quizá el último, que se ocupa de izquierda a derecha. Esa forma permite guardar el árbol en un array sin referencias explícitas.
Para un nodo en índice i:
parent = floor((i - 1) / 2)
left = 2i + 1
right = 2i + 2Ejemplo:
índice: 0 1 2 3 4 5
valor: [3, 5, 8, 10, 7, 12]La forma completa depende del array; la heap property depende del comparador.
En lugar de crear una clase para min-heap y otra para max-heap, define un comparador:
type Comparator<T> = (a: T, b: T) => number;El valor a tiene mayor prioridad que b cuando el comparador devuelve un número negativo.
const minNumber = (a: number, b: number) => a - b;
const maxNumber = (a: number, b: number) => b - a;class BinaryHeap<T> {
private readonly values: T[] = [];
constructor(private readonly compare: Comparator<T>) {}
get size(): number {
return this.values.length;
}
isEmpty(): boolean {
return this.values.length === 0;
}
peek(): T | undefined {
return this.values[0];
}
push(value: T): void {
this.values.push(value);
this.siftUp(this.values.length - 1);
}
pop(): T | undefined {
if (this.values.length === 0) return undefined;
if (this.values.length === 1) return this.values.pop();
const root = this.values[0];
this.values[0] = this.values.pop()!;
this.siftDown(0);
return root;
}
private siftUp(startIndex: number): void {
let index = startIndex;
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.compare(this.values[parentIndex], this.values[index]) <= 0) {
break;
}
this.swap(index, parentIndex);
index = parentIndex;
}
}
private siftDown(startIndex: number): void {
let index = startIndex;
while (true) {
const leftIndex = index * 2 + 1;
const rightIndex = index * 2 + 2;
let bestIndex = index;
if (
leftIndex < this.values.length &&
this.compare(this.values[leftIndex], this.values[bestIndex]) < 0
) {
bestIndex = leftIndex;
}
if (
rightIndex < this.values.length &&
this.compare(this.values[rightIndex], this.values[bestIndex]) < 0
) {
bestIndex = rightIndex;
}
if (bestIndex === index) break;
this.swap(index, bestIndex);
index = bestIndex;
}
}
private swap(a: number, b: number): void {
[this.values[a], this.values[b]] = [this.values[b], this.values[a]];
}
}Para cada índice válido i > 0:
compare(parent(i), i) <= 0El padre nunca tiene menos prioridad que su hijo.
push puede romper la propiedad solo en el camino desde el nuevo nodo hacia la raíz. siftUp corrige ese camino.
pop mueve el último valor a la raíz, por lo que puede romper la propiedad solo hacia abajo. siftDown elige en cada paso el hijo con mayor prioridad.
Sea n la cantidad de elementos:
peek: O(1), accede al índice 0.push: peor caso O(log n), porque sube como máximo la altura del árbol.pop: peor caso O(log n), porque baja como máximo la altura.O(n), la heap property no indica qué rama contiene el valor.O(n) para almacenar el heap.El árbol completo tiene altura floor(log₂ n).
Insertar n valores uno por uno cuesta O(n log n). Si ya tienes un array, puedes aplicar siftDown desde el último padre hasta la raíz.
function heapify<T>(values: T[], compare: Comparator<T>): void {
const siftDown = (start: number): void => {
let index = start;
while (true) {
const left = index * 2 + 1;
const right = index * 2 + 2;
let best = index;
if (left < values.length && compare(values[left], values[best]) < 0) {
best = left;
}
if (right < values.length && compare(values[right], values[best]) < 0) {
best = right;
}
if (best === index) return;
[values[index], values[best]] = [values[best], values[index]];
index = best;
}
};
for (let index = Math.floor(values.length / 2) - 1; index >= 0; index -= 1) {
siftDown(index);
}
}Aunque un siftDown puede costar O(log n), construir el heap completo cuesta O(n). La mayoría de nodos están cerca de las hojas y bajan muy poco; sumar esos costos produce una cota lineal.
Una priority queue define una interfaz de procesamiento por prioridad. Un binary heap es una implementación común.
type Task = {
id: string;
priority: number;
createdAt: number;
};
const tasks = new BinaryHeap<Task>((a, b) => {
const byPriority = b.priority - a.priority;
return byPriority !== 0 ? byPriority : a.createdAt - b.createdAt;
});El segundo criterio hace explícita la política de desempate. Un heap no es necesariamente estable: elementos equivalentes pueden salir en un orden distinto al de inserción.
Para conservar los k valores más grandes de un flujo, mantén un min-heap de tamaño k:
k;Tiempo: O(n log k). Memoria: O(k).
Ordenar todo costaría O(n log n) y memoria según la estrategia. El heap es mejor cuando k es mucho menor que n y no necesitas el orden completo.
La clase educativa solo inserta y extrae. Para decrease-key o update-key necesitas conocer el índice del elemento y aplicar siftUp o siftDown según el cambio.
Un Map<Id, index> puede localizar elementos, pero cada swap debe actualizar el mapa. Esa sincronización aumenta la complejidad de implementación.
En muchos algoritmos se evita decrease-key insertando una nueva entrada y descartando las obsoletas cuando salen.
Heap sort construye un max-heap y mueve repetidamente la raíz al final del array.
O(n log n) en mejor, promedio y peor caso;O(1) en su versión in-place;La estructura heap y el algoritmo heap sort comparten operaciones, pero tienen objetivos distintos.
NaN en comparadores numéricos;O(log n).siftDown en lugar del de mayor prioridad.pop.build heap como O(n log n) cuando se usa heapify bottom-up.push corrige hacia arriba; pop, hacia abajo.O(log n).¿Por qué buscar el número 7 en un min-heap puede requerir revisar todos los nodos?
Porque saber que un padre es menor que sus hijos no permite descartar una rama al buscar un valor intermedio. Ambas ramas pueden contener 7, así que en el peor caso se inspeccionan n elementos.