← Data structures from scratch · Lesson 23/32
Priority queues
The most urgent goes first
In a priority queue each item comes in with a priority number, and the one with the lowest priority (the most urgent) always comes out, not the one that arrived first. Like an emergency room: a broken bone goes before a prescription, even if the prescription came first.
It's built from a heap of [priority, data] pairs that compares only the priority. Push and pop cost O(log n). Task schedulers use it, games use it to order events by time and, in the next unit, so does Dijkstra.
$ node leccion.js
Press RUN (or Ctrl+Enter).
What to look at
They came in as cough, prescription, broken bone and fever; they leave by priority: broken bone (1), high fever (2), cough (3), prescription (5). The class is last lesson's heap, looking only at [0] of each pair.
The whole lesson on one page
The most urgent goes first
In a priority queue each item comes in with a priority number, and the one with the lowest priority (the most urgent) always comes out, not the one that arrived first. Like an emergency room: a broken bone goes before a prescription, even if the prescription came first.
It's built from a heap of [priority, data] pairs that compares only the priority. Push and pop cost O(log n). Task schedulers use it, games use it to order events by time and, in the next unit, so does 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, "cough");
urgencias.meter(5, "prescription");
urgencias.meter(1, "broken bone");
urgencias.meter(2, "high fever");
while (urgencias.tamano > 0) {
console.log(urgencias.sacar());
}
They came in as cough, prescription, broken bone and fever; they leave by priority: broken bone (1), high fever (2), cough (3), prescription (5). The class is last lesson's heap, looking only at [0] of each pair.
The k largest
A popular trick: to keep the k largest of a huge list you don't need to sort it. Use a min-heap of size k: every value goes in, and if the heap grows past k, pop the minimum. What survives are the k largest, with the smallest of them on top.
It costs O(n log k) and only stores k things. With a million values and k = 10, that's far less work than sorting the million.
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); // out goes the smallest
}
return heap;
}
const ventas = [120, 45, 300, 80, 210, 95, 400, 60];
const top = kMayores(ventas, 3);
console.log(top);
console.log("third place:", top[0]);
- 210, 300 and 400 remain, in heap order, not sorted:
[210, 400, 300]. top[0]is the smallest of the three: third place, without sorting anything.
Ties, and what other languages ship
A heap doesn't respect arrival order among equals: if two patients both have priority 2, the one who arrived later may go first. When that matters, make the priority a pair: [priority, turn], with a counter that grows on every push. Then the turn breaks the tie.
JavaScript doesn't ship a priority queue; you have to write it, like here. Other languages do: heapq in Python (a min-heap over a list), PriorityQueue in Java and priority_queue in C++ (that one's a max-heap).
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];
}
}
// The priority compares urgency first and, on a tie, the turn
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 goes first (urgency 1) and then the urgency-2 ones in arrival order: Ana, Beto, Dani, Eli. The urgencia * 1000 + turno trick packs the pair into one number (fine while there are fewer than a thousand turns); with a real pair you compare two fields.