Cola de prioridad en JavaScript

Problema

Quién va primero

El despachador de entregas reparte pedidos a los mensajeros. Cada pedido tiene un plazo: en cuántos minutos debe estar en la puerta del cliente. Un mensajero libre siempre recibe el pedido más urgente.

Los pedidos llegan todo el tiempo. Un viernes por la tarde en una gran ciudad esperan 10 000 a la vez, y pasan 100 000 en un día.

La primera solución es una lista ordenada por plazo. Con cada pedido nuevo lo añades y vuelves a ordenar la lista. Ordenar cuesta O(n log n) (mira el merge sort), y eso por cada pedido. Incluso la ordenación más lista, la que nota que la lista ya está casi ordenada, tiene que recorrerla al menos: n pasos con cada pedido nuevo.

Y el mensajero no necesita el orden de toda la lista. Solo el primero.

La idea

Una cola que solo sabe quién es el primero

Una estructura con dos acciones: añadir un pedido y tomar el más urgente. Esto es una cola de prioridad. No promete un orden para todos, solo quién va primero.

Eso es justo lo que hace el heap de la lección sobre el heap sort. Aquí está dado la vuelta: un min-heap, en el que cada padre es como mucho tan grande como sus hijos. Entonces el plazo más temprano está siempre en el índice 0.

Tomar ya lo conoces del heap sort. La cima se va, el último elemento ocupa su lugar y se hunde. La diferencia es que se hunde hacia el hijo más urgente.
Añadir es lo nuevo: subir. El pedido nuevo va al final del arreglo. Luego se compara con su padre en el índice (i - 1) / 2. Si es más urgente, intercambian los lugares y sigue subiendo. Se detiene cuando el padre es más urgente o cuando llega a la cima.

Míralo

Subir y hundir

Añadir: al final, luego hacia arriba.

push(order) {
  this.#items.push(order);
  let i = this.#items.length - 1;
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2);
    if (!this.#less(i, parent)) return;
    this.#swap(i, parent);
    i = parent;
  }
}

Tomar: la cima se va, el último ocupa su lugar y se hunde.

poll() {
  const items = this.#items;
  const top = items[0];
  items[0] = items[items.length - 1];
  items.pop();
  if (items.length > 0) this.#siftDown(0);
  return top;
}

#siftDown(i) {
  const n = this.#items.length;
  while (true) {
    let low = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < n && this.#less(left, low)) {
      low = left;
    }
    if (right < n && this.#less(right, low)) {
      low = right;
    }
    if (low === i) return;
    this.#swap(i, low);
    i = low;
  }
}

#items y #siftDown son privados: desde fuera solo ves push, poll y size.

Hay seis pedidos esperando. Entra uno nuevo con 18 minutos, y el mensajero toma el más urgente:

const waiting = [
  { id: "A-101", deadline: 10 },
  { id: "A-102", deadline: 15 },
  { id: "A-103", deadline: 30 },
  { id: "A-104", deadline: 20 },
  { id: "A-105", deadline: 25 },
  { id: "A-106", deadline: 40 },
];
const queue = new DeadlineQueue();
for (const o of waiting) queue.push(o);
console.log(`Heap: ${queue.deadlines()}`);
queue.push({ id: "A-107", deadline: 18 });
console.log(`Después de A-107: ${queue.deadlines()}`);
const next = queue.poll();
console.log(`El mensajero toma ${next.id} (${next.deadline} min)`);
console.log(`Quedan: ${queue.deadlines()}`);

Heap: [10, 15, 30, 20, 25, 40]
Después de A-107: [10, 15, 18, 20, 25, 40, 30]
El mensajero toma A-101 (10 min)
Quedan: [15, 20, 18, 30, 25, 40]

class DeadlineQueue {
  #items = [];

  push(order) {
    this.#items.push(order);
    let i = this.#items.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (!this.#less(i, parent)) return;
      this.#swap(i, parent);
      i = parent;
    }
  }

  poll() {
    const items = this.#items;
    const top = items[0];
    items[0] = items[items.length - 1];
    items.pop();
    if (items.length > 0) this.#siftDown(0);
    return top;
  }

  #siftDown(i) {
    const n = this.#items.length;
    while (true) {
      let low = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < n && this.#less(left, low)) {
        low = left;
      }
      if (right < n && this.#less(right, low)) {
        low = right;
      }
      if (low === i) return;
      this.#swap(i, low);
      i = low;
    }
  }

  #less(i, j) {
    const items = this.#items;
    return items[i].deadline < items[j].deadline;
  }

  #swap(i, j) {
    const items = this.#items;
    [items[i], items[j]] = [items[j], items[i]];
  }

  get size() {
    return this.#items.length;
  }

  deadlines() {
    const all = this.#items.map((o) => o.deadline);
    return `[${all.join(", ")}]`;
  }
}

Paso a paso, en palabras

Seis pedidos en espera, los plazos están en minutos. Un min-heap: cada padre es como mucho igual que sus hijos, por eso el más urgente, 10, está arriba.
push: un pedido nuevo con 18 minutos va al final del arreglo, índice 6. En el árbol es hijo de 30.
Subir: el padre de 6 es (6 - 1) / 2 = 2. 18 es más urgente que 30, así que se intercambian.
El padre de 2 es 0, con 10 minutos. 10 es más urgente que 18: el pedido se detiene. Un intercambio, como mucho uno por nivel.
poll: el mensajero toma la cima, el pedido de 10 minutos. En el índice 0 queda un hueco.
El último elemento, 30, salta a la cima y el arreglo se reduce a seis. Ahora #siftDown lo pone en su sitio.
Hundir, como en el heap sort pero hacia el hijo más urgente: 30 contra 15 y 18 se intercambia con 15, luego contra 20 y 25 se intercambia con 20.
El índice 3 no tiene hijos: listo. Arriba está 15, el siguiente más urgente. Ambos movimientos cuestan O(log n): la altura del árbol.

El arreglo no está ordenado: 18 va antes que 20. Solo está ordenado lo que importa: el plazo más temprano está arriba.

Pruébalo

Predice la salida

Cinco pedidos entran en una cola vacía. ¿Qué hay en el arreglo después?

const queue = new DeadlineQueue();
queue.push({ id: "B-1", deadline: 40 });
queue.push({ id: "B-2", deadline: 25 });
queue.push({ id: "B-3", deadline: 30 });
queue.push({ id: "B-4", deadline: 10 });
queue.push({ id: "B-5", deadline: 35 });
console.log(queue.deadlines());

Respuesta

[10, 25, 30, 35, 40]

[10, 25, 30, 40, 35]

[40, 25, 30, 10, 35]

Pruébalo

Completa

Al subir se compara el elemento del índice i con su padre. ¿Dónde está el padre?

const parent = ;

La idea

Cuánto cuesta

Añadir: como mucho una comparación por nivel. Un árbol de n elementos tiene unos log₂ n niveles: O(log n).
Tomar: dos comparaciones por nivel al hundir: también O(log n).
Quién va primero: la cima está en el índice 0, sin una sola comparación: O(1).

Ejecuta el despachador con las dos versiones. Los pedidos llegan uno a uno, después de cada segundo un mensajero toma el más urgente, y al final los mensajeros toman el resto. Se cuentan las comparaciones entre dos plazos:

Lista ordenada: reordenar después de cada pedido O(n²)
Montículo mínimo: subir y bajar O(n log n)

Algoritmo	n = 10	n = 1000	n = 10.000	n = 100.000
Lista ordenada: reordenar después de cada pedido	11	63.430	6.250.042	≈ 625.004.200
Montículo mínimo: subir y bajar	28	17.397	256.807	3.386.161

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

class DeadlineQueue {
  #items = [];

  push(order) {
    this.#items.push(order);
    let i = this.#items.length - 1;
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (!this.#less(i, parent)) return;
      this.#swap(i, parent);
      i = parent;
    }
  }

  poll() {
    const items = this.#items;
    const top = items[0];
    items[0] = items[items.length - 1];
    items.pop();
    if (items.length > 0) this.#siftDown(0);
    return top;
  }

  #siftDown(i) {
    const n = this.#items.length;
    while (true) {
      let low = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < n && this.#less(left, low)) {
        low = left;
      }
      if (right < n && this.#less(right, low)) {
        low = right;
      }
      if (low === i) return;
      this.#swap(i, low);
      i = low;
    }
  }

  #less(i, j) {
    const items = this.#items;
    return items[i].deadline < items[j].deadline;
  }

  #swap(i, j) {
    const items = this.#items;
    [items[i], items[j]] = [items[j], items[i]];
  }

  get size() {
    return this.#items.length;
  }

  deadlines() {
    const all = this.#items.map((o) => o.deadline);
    return `[${all.join(", ")}]`;
  }
}

Con 10 pedidos la lista ordenada hace 11 comparaciones y el heap 28: con pocos pedidos la lista está perfectamente bien. Con 10 000 son 6 250 042 contra 256 807. Con 100 000 el heap hace 3 386 161, y la lista unos 625 millones. Bench no ejecuta ese caso, lo estima a partir de la curva.

La lista ordenada de Bench está en su mejor caso: el pedido nuevo solo se desliza a su lugar, y no se ordena nada más. Aun así es O(n) por pedido, porque recorre de media la mitad de la lista. El heap es O(log n) por pedido.

Más precisamente, para curiosos

¿Qué ordenación nota que la lista ya está casi ordenada? TimSort, que usan sort en Python, List.sort y Collections.sort en Java y Array.prototype.sort en JavaScript (mira la ordenación incorporada). Encuentra la parte ordenada con unas n comparaciones y mete el elemento nuevo en ella: O(n) por pedido. Bench cuenta una variante aún más barata, deslizar desde el final, y sigue saliendo O(n). List.Sort de C# es introsort y no busca partes ordenadas: con cada pedido hace unas n log n comparaciones, todavía más.

¿Por qué subir es rápido también en la práctica? Un pedido nuevo suele estar en algún punto medio de urgencia. La mitad de los elementos de un heap son hojas, un cuarto está justo encima, y así sucesivamente. Así que, de media, un pedido al azar se detiene tras uno o dos niveles. El peor caso (el nuevo es el más urgente de todos) sigue siendo solo log₂ n.

Pruébalo

Encuentra el error

Un compañero escribió el hundimiento, pero a veces los mensajeros salen con un pedido posterior antes que con uno anterior:

#siftDown(i) {
  const n = this.#items.length;
  while (true) {
    let low = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < n && this.#less(left, low)) {
      low = left;
    }
    if (right < n && this.#less(right, i)) {
      low = right;
    }
    if (low === i) return;
    this.#swap(i, low);
    i = low;
  }
}

const queue = new DeadlineQueue();
queue.push({ id: "C-1", deadline: 5 });
queue.push({ id: "C-2", deadline: 10 });
queue.push({ id: "C-3", deadline: 20 });
queue.push({ id: "C-4", deadline: 30 });
queue.push({ id: "C-5", deadline: 40 });
queue.push({ id: "C-6", deadline: 50 });
const taken = [];
while (queue.size > 0) taken.push(queue.poll().deadline);
console.log(`[${taken.join(", ")}]`);

[5, 20, 10, 30, 40, 50]

¿En qué línea está el error?

Elige la línea con el error.

Míralo

Las colas listas de cada lenguaje

En un proyecto no escribes un heap tú mismo. Casi todos los lenguajes tienen una cola de prioridad, y cada una tiene su rareza.

JavaScript no trae ninguna cola de prioridad incorporada. Así que usamos nuestra DeadlineQueue de arriba. En un proyecto usas un paquete listo de npm o una clase corta como esta.

const queue = new DeadlineQueue();
queue.push({ id: "A-101", deadline: 30 });
queue.push({ id: "A-102", deadline: 10 });
queue.push({ id: "A-103", deadline: 20 });
queue.push({ id: "A-104", deadline: 25 });
console.log(`Por dentro: ${queue.deadlines()}`);
while (queue.size > 0) {
  const o = queue.poll();
  console.log(`${o.id} (${o.deadline} min)`);
}

Por dentro: [10, 25, 20, 30]
A-102 (10 min)
A-103 (20 min)
A-104 (25 min)
A-101 (30 min)

Más precisamente, para curiosos

Ninguna de estas colas es estable: dos pedidos con el mismo plazo pueden salir en cualquier orden (mira la estabilidad). Si el orden de llegada importa, añade un número de secuencia, como en Python arriba.

Ninguna de las tres puede cambiar el plazo de un pedido que ya espera. remove en Java busca el elemento de forma lineal: O(n). La solución habitual es añadir el pedido otra vez con el plazo nuevo y saltarse la copia vieja cuando salga. Así funciona también Dijkstra en el próximo módulo de grafos (algo-graphs).

Cómo es en los otros lenguajes: Java tiene PriorityQueue, C# PriorityQueue<TElement, TPriority> (desde .NET 6), Python heapq (funciones sobre una lista), y JavaScript no tiene ninguna cola de prioridad incorporada.

Míralo

Dos trabajos más para un heap

Los k primeros. ¿Cuáles 10 de un millón de productos se venden más? Un min-heap que nunca tiene más de 10 elementos: cada nuevo se compara con la cima. Eso está en la lección sobre el heap, también con un Bench.

Mezclar k listas ordenadas. Tres almacenes envían sus pedidos ordenados por plazo. Necesitas una ruta común, otra vez por plazo. El heap solo guarda la cabeza de cada lista. Tomas la más temprana, y en su lugar pones la siguiente del mismo almacén:

En JavaScript esta es otra vez nuestra DeadlineQueue: solo compara deadline, así que también acepta objetos que recuerdan el almacén y la posición.

const lists = [[5, 20, 45], [10, 15, 50], [12, 30]];
const names = ["Norte", "Sur", "Centro"];
const heads = new DeadlineQueue();
lists.forEach((list, k) => heads.push({ deadline: list[0], list: k, index: 0 }));
const route = [];
while (heads.size > 0) {
  const h = heads.poll();
  route.push(`${h.deadline} ${names[h.list]}`);
  const next = h.index + 1;
  if (next < lists[h.list].length) {
    heads.push({ deadline: lists[h.list][next], list: h.list, index: next });
  }
}
console.log(`Ruta: ${route.join(", ")}`);

Ruta: 5 Norte, 10 Sur, 12 Centro, 15 Sur, 20 Norte, 30 Centro, 45 Norte, 50 Sur

El heap nunca tiene más de k elementos (aquí 3). Así que N pedidos cuestan O(N log k), no O(N log N) como ordenarlo todo. Así se mezclan también las partes ordenadas de un archivo que no cabe en la memoria.

Más precisamente, para curiosos

Python tiene una mezcla lista: heapq.merge. En Java, C# y JavaScript la escribes como aquí.

El merge sort también mezcla partes ordenadas, pero de dos en dos (merge sort). Un heap mezcla k a la vez.

Ejercicio

Una cola justa

Resuelve la tarea en tu editor.

Mismo plazo, primero el anterior. Haz una cola FairQueue en la que, con plazos iguales, salga primero el pedido que llegó antes. Guarda un número de secuencia con cada pedido y compara primero por plazo, luego por número. Ejecútala con los pedidos A-1 (30), A-2 (20), A-3 (30), A-4 (20), A-5 (10), A-6 (20), en este orden:

Orden: A-5, A-2, A-4, A-6, A-1, A-3

Más tareas

Max-heap. Invierte la comparación y haz una cola que dé primero el pedido más caro.
Cuenta las comparaciones. Añade un contador a subir y a hundir y ejecuta 1000 pedidos al azar. ¿Cuántas comparaciones caen en un pedido?
Los tres primeros. ¿Cómo obtienes los tres pedidos más urgentes sin sacar los demás de la cola?

Test

Ponte a prueba

1. ¿Qué promete una cola de prioridad?Saca los elementos en el orden en que llegaronSaca el elemento más urgente y acepta nuevos, sin ordenarlo todoMantiene los elementos ordenados para que puedas recorrerlos en orden

2. Un pedido nuevo entra en un heap de 1 000 000 de pedidos. ¿Cuántas comparaciones hace como máximo al subir?Unas 1000Unas 1 000 000Unas 20

3. En Python guardas los pedidos como (plazo, dict) en heapq. Dos pedidos tienen el mismo plazo. ¿Qué pasa?TypeError: las tuplas se comparan por su segundo elemento, y los dict no se pueden compararSe toma el que entró primeroheapq los fusiona en uno

4. Tres almacenes envían listas ordenadas por plazo, N pedidos en total. ¿Cómo las mezclas en una sola ruta?Las unes en una lista y la ordenasUn heap con la cabeza de cada lista: tomas el más temprano y pones el siguiente del mismo almacénTomas uno de cada almacén por turnos

Cola de prioridad

Cookies