Heap / Priority Queue

Almost every problem in this topic is secretly the same question in disguise: "give me the best (or worst) k things, without fully sorting everything." A heap answers that question in O(log n) per operation instead of paying for a full sort — and recognizing when a problem has that shape is most of the skill here.

What a heap actually is

A heap is a complete binary tree, stored flat in an array, satisfying one invariant: every parent is ≤ every child (min-heap) or ≥ every child (max-heap). That's a much weaker guarantee than a sorted array — a heap only promises the root is the smallest (or largest) element, not that anything else is in any particular order. That weaker guarantee is exactly what makes push/pop cheap: fixing the invariant after a change only ever touches one root-to-leaf path, which is O(log n), rather than re-sorting everything.

std::priority_queue is a max-heap by default

std::priority_queue<int> gives you the largest element on top. For a min-heap, flip the comparator: std::priority_queue<int, std::vector<int>, std::greater<int>>. This trips people up constantly, because the comparator you pass answers "does a come before b" in the sense of sorted order, but a max-heap is what you get from the default (less) comparator — it feels backwards the first few times.

// The single most common shape in this entire topic: keep only the best
// k elements seen so far, in O(log k) per element instead of O(log n).
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap; // smallest on top
for (int x : nums) {
    min_heap.push(x);
    if (min_heap.size() > k) min_heap.pop(); // evict the current worst of the top-k
}
// min_heap.top() is now exactly the k-th LARGEST element seen -- everything
// that got popped was, at the moment it was popped, worse than every
// candidate still in the heap.

The bounded-heap-of-size-k pattern

Kth Largest Element in a Stream, Kth Largest Element in an Array, K Closest Points to Origin, and Top K Frequent Elements are all the exact same trick wearing different clothes: cap a heap at size k, and whatever's left when you're done is the answer. The heap holds the opposite extreme of what you're keeping — a min-heap when you want the k largest, a max-heap when you want the k closest (smallest distances) — because you always want to evict the worst of your current best-k candidates, and "worst of the best" sits on top of the heap that orders by the opposite direction.

The frontier-expansion pattern (multi-way merge)

Find K Pairs with Smallest Sums, Kth Smallest Element in a Sorted Matrix, and Super Ugly Number all share a different shape: instead of one already-known collection, you have several sorted sequences (rows of a matrix, or one sequence per prime) and want to walk them in combined sorted order without merging all of them upfront. Seed a heap with each sequence's current smallest candidate; every time you pop one, push that same sequence's next value. This touches only as many elements as you actually need — never the full cross product or the full matrix.

Two heaps, split down the middle

Find Median from Data Stream needs the middle of a constantly-changing collection, which neither pattern above directly gives you. The fix: keep two heaps — a max-heap for the lower half, a min-heap for the upper half — balanced so their sizes never differ by more than one. The median is then just the top of one heap, or the average of both tops. IPO uses two heaps for a different reason: one sorted structure to track "what's newly affordable," and a max-heap to always grab the most profitable currently affordable option — two different jobs, each suited to a different structure.

Common mistakes

• Sorting when you only needed a bounded heap — Kth Largest Element in an Array doesn't need the array fully sorted; a min-heap capped at size k does O(n log k) instead of O(n log n), and the gap widens a lot once k is much smaller than n.
• Repeatedly rescanning for the current max/min instead of maintaining a heap — the instinct to "just scan for the best one again" turns an O(log n)-per-step problem into O(n) per step, and O(n²) or O(n·k) overall (Last Stone Weight, Kth Largest Element in an Array, IPO all specifically guard against this).
• Forgetting std::priority_queue defaults to a max-heap — passing no comparator when you actually wanted the smallest element on top is a silent logic bug, not a compile error.
• Materializing the full cross product when a frontier-expansion heap would do — Find K Pairs with Smallest Sums doesn't need all n₁·n₂ pairs, just the k smallest, and generating everything upfront can blow past a reasonable memory budget for no benefit.