Patterns / Heaps & Top-K

Heaps & Top-K Pattern

A heap keeps the largest or smallest element reachable in O(log n) — ideal for "top K" and merging streams.

What it is

A heap (priority queue) always gives you the minimum or maximum in O(1) and supports insertion and removal in O(log n). For "top K" problems you keep a heap of size K: a min-heap of the K largest seen so far, evicting the smallest whenever a bigger element arrives. This processes a stream in O(n log k) without sorting everything, and the same structure elegantly merges multiple sorted sources.

When to use it — the signals

• "K largest / smallest", "K most frequent", "K closest".
• Merging several sorted lists or streams.
• Repeatedly needing the current min/max as data changes.

How it works

A representative implementation in Java:

// K largest elements using a min-heap of size k.
PriorityQueue<Integer> heap = new PriorityQueue<>();   // min-heap
for (int x : nums) {
    heap.offer(x);
    if (heap.size() > k) heap.poll();   // drop the smallest
}
return heap;   // contains the k largest

Complexity

O(n log k) to scan with a size-k heap; O(1) to peek the extreme. Space is O(k).

Common pitfalls

• Using a max-heap when a min-heap of size k is what bounds memory.
• Comparator direction mistakes (Java PriorityQueue is a min-heap by default).
• Reaching for a full sort when only the top K are needed.

Practice problems

Classic problems where this pattern is the intended approach: Kth Largest Element in an Array, Top K Frequent Elements, K Closest Points to Origin, Merge k Sorted Lists. Work through them on the Leet Study home page.