Heaps: The Top of the Pile Without Sorting It

Sorting is overkill for a surprising number of problems. If all you ever ask is “what’s the smallest right now” — and then you pull it out, and ask again — you don’t need the other $n - 1$ elements in order; you need a structure that keeps the extreme at your fingertips and shrugs off the rest. That’s a heap: the minimum (or maximum) in $O(1)$, insert and remove in $O(\log n)$, and no promise whatsoever about the order of everything else. A PriorityQueue in Java is exactly this, and the whole category is about noticing when “just the extreme” is all the order you need.

How it stays cheap

You never actually build the tree a heap describes — you pack it into an array, where the node at index i keeps its children at 2i+1 and 2i+2. Inserting sifts the new value up one root-to-leaf path; removing the top drops a value in and sifts it down the same way. Both touch at most $\log n$ nodes, and that single-path cost is the whole efficiency story: you spend $O(\log n)$ to restore the one property that matters — the extreme sits at the root — and nothing keeping the rest in order. Building a heap from an existing array is cheaper still, $O(n)$ — part of why a heap can beat sorting when you only need the extremes rather than a full order (sorting still solves several of these, just usually with more work).

The size-k heap, which feels backwards

The signature heap trick is the one that looks wrong the first time: to track the k-th largest element, you keep a min-heap — of size k. Its top is the smallest of your k biggest, which is precisely the k-th largest overall, and the moment the heap grows past k you evict that smallest top. Anything you evict was too small to ever be in the top k, so you never look at it again:

PriorityQueue<Integer> heap = new PriorityQueue<>();   // min-heap
for (int x : nums) {
    heap.offer(x);
    if (heap.size() > k) heap.poll();   // drop the smallest; it can't be top-k
}
return heap.peek();                     // the k-th largest

That bounded heap is why Kth Largest Element in an Array, Kth Largest Element in a Stream (which answers the query after every insert), and K Closest Points to Origin all cost $O(n \log k)$ instead of a full $O(n \log n)$ sort. When k is small and n is huge — top 10 of a billion — that gap is the whole point.

Two heaps balance a median

The running-median problem is the elegant one. Split the numbers into a low half and a high half: a max-heap holds the low half so its top is the largest small number, and a min-heap holds the high half so its top is the smallest large number. Keep the two heaps’ sizes within one of each other, and the median is sitting at the top of one of them (or the average of both tops). Every insert rebalances in $O(\log n)$, so Find Median from Data Stream answers each query in $O(1)$ after an $O(\log n)$ add — a heap where a sort would have to redo its work on every new number.

Frequency and merging

The rest lean on the same “give me the current extreme” service, but over a full heap rather than a size-k one. Last Stone Weight loads every stone into a max-heap and repeatedly smashes the two heaviest, pushing back their difference until one or none remains — $O(n \log n)$, because each round needs the true maximum, not a top-k cutoff. Task Scheduler puts task counts in a max-heap and repeatedly schedules the most frequent task that isn’t cooling down — a greedy choice that spaces the hot tasks out. Design Twitter merges each followed user’s most recent posts through a heap, the same k-way merge that stitches k sorted lists together — the heap always surfaces the newest post across all the feeds.

You’re already scheduling with one

A priority queue is the beating heart of a scheduler. A runtime that runs “do this in 5 seconds” often keeps a min-heap of deadlines and sleeps until the earliest one — Java’s ScheduledThreadPoolExecutor works this way (though at very high timer counts some networking stacks switch to a bucketed timer wheel, which trades the heap for time-slot buckets). Dijkstra’s shortest path pulls its frontier from a min-heap, and priority-based schedulers order runnable work the same way. In practice I default to java.util.PriorityQueue and spend the thought on the comparator and what goes in it, not on the heap itself — a queue that drifts out of order quietly serves the wrong thing first.

When “sorted” is more than you need

The tell for this category is a question that only ever touches the extreme of a changing set: the largest, the smallest, the k-th, the median, the most frequent. A full sort answers those too, but it pays to order elements you’ll never compare, and it can’t cheaply absorb a new element into an already-sorted result. A heap keeps exactly the structure the question needs and no more — which, when the set is a stream or k is tiny, is the difference between $O(n \log k)$ and starting over.

References

• NeetCode 150 — Heap / Priority Queue — the seven problems collected here.