Priority queues in practice

A priority queue is the ADT; a heap is how you implement it. Instead of first-in-first-out, the highest-priority item is served next.

const queue = new MinHeap((a, b) => a.priority - b.priority);

queue.push({ priority: 3, job: 'send digest email' });
queue.push({ priority: 1, job: 'password reset' });
queue.push({ priority: 2, job: 'resize avatar' });

queue.pop();   // the password reset — priority 1 wins

Ties need a rule

Heaps are not stable: two items with equal priority come out in unspecified order. When arrival order matters, add a monotonically increasing counter as a tiebreaker:

let sequence = 0;
const queue = new MinHeap((a, b) => a.priority - b.priority || a.seq - b.seq);

const enqueue = (priority, job) => queue.push({ priority, seq: sequence++, job });

Without it, a job can sit behind newer jobs of the same priority indefinitely, and the bug is intermittent and very hard to reproduce.

Starvation

Strict priority means low-priority work may never run while high-priority work keeps arriving. Real schedulers add ageing: raise an item's priority the longer it waits.

const effective = (job, now) => job.priority - Math.floor((now - job.queuedAt) / 60_000);

This is not a data-structure problem — the heap is doing exactly what it was asked. It is a policy problem, and naming it in a system design interview scores well.

Where you will meet one

• Dijkstra and A* — always expand the nearest unvisited node.
• Task schedulers and event loops — the next timer to fire is a min-heap by timestamp.
• Huffman coding — repeatedly merge the two least frequent symbols.
• Merging k sorted streams — a heap of the current heads.
• Rate limiting and expiry — the soonest-to-expire entry.

Updating a priority

Changing an item's priority after insertion needs decreaseKey, which requires knowing where the item sits — a heap alone cannot find it. Two options: keep a map from item to index and update it on every swap, or push a new entry and skip stale ones on pop:

const [priority, node] = queue.pop();
if (priority > best[node]) continue;    // stale entry, already improved

The lazy version is what most Dijkstra implementations do, because it is far simpler and costs only a little extra memory.