Priority Queues

An ordinary queue is fair: first in, first out. A priority queue is not fair — it is sensible. Every item carries a priority, and the item served next is always the one with the best priority, no matter when it arrived. Think of a hospital emergency room: patients are seen by how urgent they are, not by who walked in first.

Two operations define it:

Everything else — how the items are stored inside — is an implementation detail chosen to make those two operations fast.

A priority queue in code

The simplest version just keeps items in a list and scans for the smallest each time. It's easy to read, and enough to see the behaviour — the item with the lowest priority number always leaves first, whatever order they went in. Press Run:

interface Item { name: string; priority: number; // smaller = more urgent } class PriorityQueue { private items: Item[] = []; insert(name: string, priority: number): void { this.items.push({ name, priority }); } extractMin(): Item | undefined { if (this.items.length === 0) return undefined; // Find the index of the smallest priority, then remove it. let best = 0; for (let i = 1; i < this.items.length; i++) { if (this.items[i].priority < this.items[best].priority) best = i; } return this.items.splice(best, 1)[0]; } get size(): number { return this.items.length; } } const pq = new PriorityQueue(); pq.insert("email", 5); pq.insert("fire alarm", 1); pq.insert("lunch", 4); pq.insert("phone call", 2); // They come out in priority order, not arrival order: while (pq.size > 0) { console.log(pq.extractMin()!.name); }

"fire alarm" jumps the queue even though it arrived second, and "email" waits even though it was first. That is the whole point.

Making it fast: the heap

Scanning the whole list for the minimum costs about N steps every time. A real priority queue stores its items in a binary heap — a tree kept in an array where every parent is smaller than its children. The smallest item is then always at the root, so extract-min is instant, and both insert and extract-min cost only about \log N steps to restore the ordering.

Dijkstra's algorithm repeatedly asks "which unvisited vertex is closest?" — exactly an extract-min. Answer it by scanning and the algorithm costs about V^2; answer it with a heap-backed priority queue and it drops to about (V + E)\log V. Same algorithm, a far faster satnav — the priority queue is doing the heavy lifting. The same trick powers A* search and Huffman coding.