← Estructuras de datos desde cero · Lección 23/32
Colas de prioridad
Sale el más urgente
En una cola de prioridad cada cosa entra con un número de prioridad, y siempre sale la de prioridad más baja (la más urgente), no la que llegó primero. Como en urgencias: una fractura pasa antes que una receta, aunque la receta haya llegado antes.
Se arma con un montículo de parejas [prioridad, dato] que compara sólo la prioridad. Meter y sacar cuestan O(log n). La usan los planificadores de tareas, los juegos que ordenan eventos por tiempo y, en la siguiente unidad, Dijkstra.
$ node leccion.js
Pulsa CORRER (o Ctrl+Enter).
Qué mirar
Entraron tos, receta, fractura y fiebre; salen por prioridad: fractura (1), fiebre alta (2), tos (3), receta (5). La clase es el montículo de la lección anterior, mirando sólo [0] de cada pareja.
Toda la lección en una página
Sale el más urgente
En una cola de prioridad cada cosa entra con un número de prioridad, y siempre sale la de prioridad más baja (la más urgente), no la que llegó primero. Como en urgencias: una fractura pasa antes que una receta, aunque la receta haya llegado antes.
Se arma con un montículo de parejas [prioridad, dato] que compara sólo la prioridad. Meter y sacar cuestan O(log n). La usan los planificadores de tareas, los juegos que ordenan eventos por tiempo y, en la siguiente unidad, Dijkstra.
class ColaPrioridad {
constructor() { this.heap = []; }
get tamano() { return this.heap.length; }
meter(prioridad, dato) {
const h = this.heap;
h.push([prioridad, dato]);
let i = h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (h[p][0] <= h[i][0]) break;
[h[p], h[i]] = [h[i], h[p]];
i = p;
}
}
sacar() {
const h = this.heap;
const arriba = h[0];
const ultimo = h.pop();
if (h.length > 0) {
h[0] = ultimo;
let i = 0;
while (true) {
const a = 2 * i + 1, b = 2 * i + 2;
let m = i;
if (a < h.length && h[a][0] < h[m][0]) m = a;
if (b < h.length && h[b][0] < h[m][0]) m = b;
if (m === i) break;
[h[m], h[i]] = [h[i], h[m]];
i = m;
}
}
return arriba[1];
}
}
const urgencias = new ColaPrioridad();
urgencias.meter(3, "tos");
urgencias.meter(5, "receta");
urgencias.meter(1, "fractura");
urgencias.meter(2, "fiebre alta");
while (urgencias.tamano > 0) {
console.log(urgencias.sacar());
}
Entraron tos, receta, fractura y fiebre; salen por prioridad: fractura (1), fiebre alta (2), tos (3), receta (5). La clase es el montículo de la lección anterior, mirando sólo [0] de cada pareja.
Los k más grandes
Un truco muy usado: para quedarte con los k más grandes de una lista enorme no hace falta ordenarla. Se usa un montículo mínimo de tamaño k: cada valor entra, y si el montículo pasa de k, se saca el mínimo. Lo que sobrevive son los k más grandes, y arriba está el más chico de ellos.
Cuesta O(n log k) y sólo guarda k cosas. Con un millón de valores y k = 10, es mucho menos trabajo que ordenar el millón.
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 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 meter(heap, valor) {
heap.push(valor);
subir(heap, heap.length - 1);
}
function sacar(heap) {
const min = heap[0];
const ultimo = heap.pop();
if (heap.length > 0) {
heap[0] = ultimo;
bajar(heap, 0);
}
return min;
}
function kMayores(arr, k) {
const heap = [];
for (const x of arr) {
meter(heap, x);
if (heap.length > k) sacar(heap); // fuera el más chico
}
return heap;
}
const ventas = [120, 45, 300, 80, 210, 95, 400, 60];
const top = kMayores(ventas, 3);
console.log(top);
console.log("el tercer lugar:", top[0]);
- Quedan 210, 300 y 400, en orden de montículo, no ordenados:
[210, 400, 300]. top[0]es el más chico de los tres: el tercer lugar, sin ordenar nada.
Empates, y lo que traen otros lenguajes
Un montículo no respeta el orden de llegada entre iguales: si dos pacientes tienen prioridad 2, puede salir primero el que llegó después. Cuando eso importa, la prioridad se hace pareja: [prioridad, turno], con un contador que crece en cada meter. Así el empate lo rompe el turno.
JavaScript no trae cola de prioridad; hay que escribirla, como aquí. Otros lenguajes sí: heapq en Python (un montículo mínimo sobre una lista), PriorityQueue en Java y priority_queue en C++ (ésta, de máximos).
class ColaPrioridad {
constructor() { this.heap = []; }
get tamano() { return this.heap.length; }
meter(prioridad, dato) {
const h = this.heap;
h.push([prioridad, dato]);
let i = h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (h[p][0] <= h[i][0]) break;
[h[p], h[i]] = [h[i], h[p]];
i = p;
}
}
sacar() {
const h = this.heap;
const arriba = h[0];
const ultimo = h.pop();
if (h.length > 0) {
h[0] = ultimo;
let i = 0;
while (true) {
const a = 2 * i + 1, b = 2 * i + 2;
let m = i;
if (a < h.length && h[a][0] < h[m][0]) m = a;
if (b < h.length && h[b][0] < h[m][0]) m = b;
if (m === i) break;
[h[m], h[i]] = [h[i], h[m]];
i = m;
}
}
return arriba[1];
}
}
// La prioridad compara primero la urgencia y, si empatan, el turno
let turno = 0;
const prioridad = (urgencia) => urgencia * 1000 + turno++;
const cola = new ColaPrioridad();
for (const [urgencia, quien] of [[2, "Ana"], [2, "Beto"], [1, "Caro"], [2, "Dani"], [2, "Eli"]]) {
cola.meter(prioridad(urgencia), quien);
}
const orden = [];
while (cola.tamano > 0) orden.push(cola.sacar());
console.log(orden);
Caro sale primero (urgencia 1) y luego los de urgencia 2 en el orden en que llegaron: Ana, Beto, Dani, Eli. El truco de urgencia * 1000 + turno mete la pareja en un solo número (vale mientras haya menos de mil turnos); con la pareja de verdad se comparan dos campos.