2Brute2Best
🔥0

Heap — Top K Pattern: Algorithmic Intuition, Sub-patterns & C++ Guide

Keep a heap of size K so you always know the K best items without sorting everything.

4 sub-patterns · 12 questions

Remember this · Heap — Top K
Trigger
"K largest / smallest / most frequent / closest", kth element, streaming top-K.
Think
Do I really need everything sorted, or only the best K?
Key question
Min-heap or max-heap of size K — which one lets me kick out the worst candidate?
A

What is this pattern?

The question wants only the best K items: the K largest, the K most frequent, the K closest, or just the Kth one. Sorting everything costs O(N log N) and then throws most of the work away.

Instead, keep a heap of size K holding the best K items seen so far. The trick is the heap's direction. To keep the K largest, use a min-heap: its top is the weakest member of the club, the one to kick out when something better arrives. To keep the K smallest, use a max-heap for the same reason.

Each of the N items costs at most one push and one pop on a heap of size K, so the total is O(N log K) time and O(K) space. When the K best are scored by something else (a count, a distance), compute the score first and put (score, item) in the heap.

A team that only has room for K players. When a new player tries out, you don't compare them with everyone. You compare them with the weakest player on the team. If the newcomer is better, the weakest is cut and the newcomer joins. The coach keeps the weakest player in view: that's the top of a min-heap.

B

See it move

Heap shown in pop order, top on the left; a real heap stores it as a tree. In nums, blue = in the heap now, red = evicted or skipped.

K largest with a min-heap of size Knums = [5,1,8,3,9,2,7,6], k = 3step 1/10
nums
0
1
2
3
4
5
6
7
5
1
8
3
9
2
7
6
min-heap (size ≤ 3)
State
k
3
heap size
0
Keep the 3 largest seen so far

Walk nums once. The heap holds the 3 largest values seen so far, and its top is the smallest of them: the one to kick out when something bigger arrives.

`4:4` means value 4 appears 4 times. Heap shown in pop order, top (least frequent kept) on the left.

Top K frequent: count first, then heap by countnums = [4,1,4,2,1,4,3,2,4,1], k = 2step 1/6
nums
0
1
2
3
4
5
6
7
8
9
4
1
4
2
1
4
3
2
4
1
count
1:32:23:14:4
Step 1: count every value

First count each value with a hash map: 1 appears 3×, 2 appears 2×, 3 appears 1×, 4 appears 4×. Now the rank of a value is its count, not its size.

C

How do I recognise it?

  • "K largest / K smallest / Kth largest / Kth smallest" in an unsorted collection.

  • "K most frequent", "top K words", "sort by frequency".

  • "K closest" points, values or elements to some target.

  • A stream of numbers arrives one at a time and you must answer "Kth largest so far" after each.

  • "Repeatedly take the largest (or smallest)", change it, and put it back (Last Stone Weight).

  • "Give out the smallest free ID / seat / number", where returned items come back into play.

Looks like Heap — Top K, but isn't

K sorted lists, merge them or find the Kth smallest across them
→ K-way Merge

The lists are already sorted, so the heap holds one front per list, not the K best items. The question is "which list goes next?", not "is this item good enough to keep?".

Median of a stream
→ Two Heaps

The median sits in the middle, not at the top. One heap can't reach it; two heaps (a lower half and an upper half) can.

K closest elements in a **sorted** array
→ Binary Search

In a sorted array, the K closest always form one contiguous window. Binary search for the window's left edge: O(log N + K), better than a heap's O(N log K).

Maximum of every window of size K
→ Sliding Window (monotonic deque)

Items also leave the window in arrival order. A deque drops them in O(1); a heap can't remove an old item from the middle.

D

How would I discover it from scratch?

Don't memorise “use heap — top k”. Ask these questions in order — the pattern falls out.

Sort everything and take the first K: O(N log N). It also does work you never needed, since the order of everything outside the top K doesn't matter.

E

Sub-patterns

Same core idea, different rule for “valid”. Learn them in this order.

01

Kth element

4 questions

Find the Kth largest (or the K largest) in an unsorted collection, or keep pulling the current largest out.

02

Top K by frequency

3 questions

The rank is how often an item appears. Count first with a hash map, then pick the K best counts with a heap (or bucket by count).

03

Closest / distance

2 questions

The rank is a distance to some target. Score each item, then keep the K smallest scores with a max-heap.

04

Streaming / dynamic

3 questions

A class answers queries while items arrive (or are taken and returned). Keep the heap alive between calls so each call is O(log K) or O(log N).

F

Don't mix these up

K largest → min-heap vs K smallest → max-heap

The heap's top is the item you'll throw out next. To keep the largest, throw out the smallest kept one: min-heap. To keep the smallest (or closest), throw out the largest: max-heap.

Size-K heap vs Heap of everything

Pushing all N items and popping K is O(N + K log N), and it needs O(N) memory. The size-K heap uses O(K) memory and works on a stream you can't store. Prefer it unless K is close to N.

Top K (heap) vs Bucket sort

When the rank is a count, counts are between 1 and N, so buckets give O(N). When the rank is a value or a distance with no small bound, use the heap.

G

Code templates (C++)

K largest with a size-K min-heap

Push every item; when the size passes K, pop. The heap's top is the Kth largest. For the K smallest, flip to a max-heap (drop greater<>).

kth-largest-template.cpp
// Kth largest: keep the k largest seen so far in a min-heap of size k.
int findKthLargest(vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> pq;     // min-heap: top = weakest of the k
    for (int x : nums) {
        pq.push(x);
        if ((int)pq.size() > k) pq.pop();                   // kick out the smallest
    }
    return pq.top();                                        // the kth largest
}

Top K by frequency

Count with a hash map, then keep a size-K min-heap of (count, value), keyed on the count, not the value. The bucket version (bucket[c] = values seen c times) is O(N).

top-k-frequent-template.cpp
// Top k frequent: count first, then a size-k min-heap keyed on the COUNT.
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    for (int x : nums) cnt[x]++;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;  // (count, value)
    for (auto& [v, c] : cnt) {
        pq.push({c, v});
        if ((int)pq.size() > k) pq.pop();                   // drop the least frequent
    }
    vector<int> out;
    while (!pq.empty()) { out.push_back(pq.top().second); pq.pop(); }
    return out;                                             // least -> most frequent
}

K closest with a size-K max-heap

Score each item by its distance (squared, so no sqrt). To keep the K smallest distances, the top must be the farthest kept item, so use a max-heap.

k-closest-template.cpp
// K closest points to the origin: a MAX-heap of size k keyed on squared distance.
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
    priority_queue<pair<long long, int>> pq;                // (dist^2, index); top = farthest kept
    for (int i = 0; i < (int)points.size(); i++) {
        long long d = 1LL * points[i][0] * points[i][0] + 1LL * points[i][1] * points[i][1];
        pq.push({d, i});
        if ((int)pq.size() > k) pq.pop();                   // kick out the farthest
    }
    vector<vector<int>> out;
    while (!pq.empty()) { out.push_back(points[pq.top().second]); pq.pop(); }
    return out;
}

Streaming Kth largest

The same size-K min-heap, kept alive inside a class. Each add is O(log K), and the answer is always the top.

stream-template.cpp
// Kth largest in a stream: the size-k min-heap lives inside the class.
class KthLargest {
    int k;
    priority_queue<int, vector<int>, greater<int>> pq;     // the k largest so far
public:
    KthLargest(int k, vector<int>& nums) : k(k) {
        for (int x : nums) add(x);
    }
    int add(int val) {
        pq.push(val);
        if ((int)pq.size() > k) pq.pop();
        return pq.top();                                    // O(log k) per call
    }
};
Next
Start with Kth element