Heaps: Top-K, K-Way Merge, Two Heaps

Intermediate · 22 min read · Problem-Solving Patterns, Heaps

Keep only k items, merge sorted streams, and track a running median.

A heap (PriorityQueue in Java) answers one question very fast, again and again: "what's the smallest (or largest) right now?" — O(1) to peek, O(log n) to add or remove. Sorting gives you the full order once; a heap gives you the extreme element repeatedly, while items keep arriving and leaving.

Heap basics in Java

A heap is not sorted — only the top is guaranteed. Iterating a PriorityQueue does not give sorted order; poll repeatedly if you need that.

Pattern 1: Top-k — keep a heap of size k

To find the k largest, keep a min-heap of size k. That sounds backwards, but the top of the min-heap is the weakest of your current top k — exactly the one to evict when a better element arrives.

Pattern 2: K-way merge — one candidate per list

To merge k sorted lists, the next output is the smallest of the k current heads. Keep exactly those k heads in a min-heap; after taking one, push its successor from the same list.

Pattern 3: Two heaps — the running median

Split the numbers into a lower half (max-heap, so its largest is on top) and an upper half (min-heap, its smallest on top). Keep the sizes balanced; the median is at the tops.

Pattern 4: Repeatedly take the best

Some problems are just "take the top, process it, maybe push something back", until done:

Practice ladder

Interview questions

  • Why use a min-heap to find the k largest elements?
  • What's the complexity of merging k sorted lists with a heap, and why is it better than merging them one by one?

Further reading

Key takeaways

  • A heap gives the current min or max in O(1) and updates in O(log n) — ideal when you need the extreme repeatedly.
  • Top-k: a size-k heap whose top is the one to evict (k largest → min-heap). O(n log k).
  • K-way merge: one head per list in a min-heap; push the successor after each pop. O(N log k).
  • Two heaps (max-heap lower half, min-heap upper half) maintain a running median.
  • Use Integer.compare; remember a PriorityQueue is not sorted when iterated.

Previous: Monotonic Stack & Queue · Next: Tree DFS: Think in Subtrees