Heaps and Priority Queues: The Structure Behind "What's Next"

A hospital emergency room doesn't call patients in the order they walked through the door — a patient with a life-threatening injury who arrived five minutes ago gets seen before someone with a minor sprain who's been waiting an hour. That's a priority queue: a line where "next" is determined by urgency, not arrival order, and a heap is the data structure most commonly used to implement one efficiently.

A priority queue is an abstract idea — a collection where you can add items with some priority and always retrieve the highest (or lowest) priority item next — and it can be built several ways. A heap is the specific structure that makes both operations fast: it's a binary tree with one strict rule, that every parent node's priority is higher (or lower, depending on the variant) than both of its children's, all the way down the tree. That single rule guarantees the item at the very top is always the highest-priority one, without needing to sort the entire collection.

Because a heap only enforces that parent-child relationship — not a full sorted order across every level — adding a new item or removing the top item both only require walking a single path up or down the tree, not touching every element. That's what makes a heap fast: both operations run in O(log n) time, the height of the tree, rather than the O(n) an approach that scans for the highest priority every time would need.

Heaps show up constantly once you know to look for them: Dijkstra's algorithm, covered elsewhere in this category, uses a priority queue to always expand the closest unvisited node next rather than checking every remaining node from scratch; operating system schedulers use one to decide which waiting process gets the CPU next; and heapsort — a genuine, comparison-based sorting algorithm in its own right — works by repeatedly pulling the top item off a heap built from the whole input.

The core intuition worth keeping: whenever a problem needs "give me the current best, worst, or most-urgent item, then let me add more, and repeat," a heap-backed priority queue is almost always the right tool, precisely because it's built to answer that one question fast without needing everything fully sorted at every step along the way.