Heaps y colas de prioridad

Si sólo necesitás retirar siempre la tarea más urgente, ordenar toda la colección después de cada cambio es trabajo de más. Un heap mantiene justo la información necesaria para acceder a la mejor prioridad rápidamente.

Las dos invariantes de un heap

Un heap binario combina dos invariantes. Su forma es un árbol completo: todos los niveles están llenos salvo quizá el último, que se ocupa de izquierda a derecha. En un min-heap, la clave de cada padre es menor o igual que la de sus hijos.

Eso garantiza que el mínimo está en la raíz. No garantiza que hermanos ni subárboles estén ordenados entre sí.

Sin punteros: la aritmética de índices

La forma completa permite omitir punteros y guardar los nodos en un arreglo. Para una posición $i$ comenzando en cero, el padre se calcula cuando $i>0$:

Las relaciones salen de los índices. La representación es compacta y aprovecha localidad de memoria.

Insertar y subir

Para insertar, agregamos el nuevo valor al final, única posición que conserva la forma completa. Si viola el orden con su padre, los intercambiamos y repetimos hacia arriba. Este proceso se llama ascenso o sift up.

Como el camino hasta la raíz tiene altura $O(\log n)$, insertar cuesta $O(\log n)$. Consultar el mínimo sólo lee la raíz y cuesta $O(1)$.

Extraer y bajar

Para extraer el mínimo, guardamos la raíz, movemos el último elemento a su lugar y reducimos el arreglo. Luego lo intercambiamos con el menor de sus hijos mientras viole la invariante. Ese descenso, o sift down, cuesta $O(\log n)$.

Elegir el hijo menor es esencial: intercambiar con cualquiera puede dejar al nuevo padre por encima de una clave todavía menor.

Construirlo de una vez sale lineal

Insertar $n$ elementos uno por uno cuesta $O(n\log n)$. Pero si ya tenemos todos los datos, podemos construir el heap desde el último nodo con hijos y aplicar descensos hacia la raíz. Ese algoritmo cuesta $O(n)$.

Aunque parece haber muchos descensos, la mayoría de los nodos está cerca de las hojas y baja muy pocos niveles. Sólo una fracción pequeña puede recorrer toda la altura.

Dónde aparece una cola de prioridad

Una cola de prioridad expone insertar, consultar y extraer la mejor prioridad; el heap es su implementación habitual. Aparece en planificación de tareas, Dijkstra, simulación de eventos y selección de los $k$ mejores elementos.

No sirve para buscar una clave arbitraria en tiempo logarítmico. Su orden es parcial, diseñado para optimizar un extremo, no para recorrer todo en orden.

Un heap binario, escrito

Todo el heap vive en un arreglo, y las relaciones de padre e hijo son aritmética de índices.

class MinHeap {
  private readonly values: number[] = [];

  private static parentOf(index: number): number {
    return Math.floor((index - 1) / 2);
  }

  push(value: number): void {
    this.values.push(value);
    let index = this.values.length - 1;

    while (index > 0) {
      const parent = MinHeap.parentOf(index);
      if (this.values[parent]! <= this.values[index]!) break; // ya está en su lugar
      [this.values[parent], this.values[index]] = [this.values[index]!, this.values[parent]!];
      index = parent;
    }
  }

  pop(): number | undefined {
    if (this.values.length === 0) return undefined;
    const top = this.values[0]!;
    const last = this.values.pop()!;
    if (this.values.length === 0) return top;

    this.values[0] = last;
    let index = 0;

    while (true) {
      const left = index * 2 + 1;
      const right = left + 1;
      let smallest = index;

      if (left < this.values.length && this.values[left]! < this.values[smallest]!) smallest = left;
      if (right < this.values.length && this.values[right]! < this.values[smallest]!) smallest = right;
      if (smallest === index) break;

      [this.values[smallest], this.values[index]] = [this.values[index]!, this.values[smallest]!];
      index = smallest;
    }

    return top;
  }
}

Los dos ciclos son la estructura entera. El de push sube el valor nuevo mientras sea menor que su padre; el de pop baja el último valor —que quedó arriba— mientras alguno de sus hijos sea menor. Los dos recorren como mucho la altura del árbol, que es $\log n$ porque el árbol es completo, y ahí está el $O(\log n)$ de las dos operaciones.

Para qué sirve tener sólo el mínimo

Cierre

El heap evita ordenar información que no necesitamos. Su forma completa habilita un arreglo; su orden parcial deja el mejor elemento en la raíz. Consultar cuesta $O(1)$, insertar y extraer $O(\log n)$, y construir desde todos los datos puede hacerse en $O(n)$.