Top K Frequent Elements Using Heap in DSA C++

Mental Model

We find the elements that appear most often by counting them, then keep only the top K using a small container that quickly removes the least frequent.

Analogy: Imagine you have a basket of fruits and want to keep only the top K types that appear most. You count each fruit type, then use a small box that always throws out the fruit type with the least count when full, so you end up with the top K types.

Frequency map: {apple:3, banana:5, orange:2}
Min-heap (size K=2):
  banana(5)
  apple(3)
  (orange(2) discarded because heap full and less frequent)

Dry Run Walkthrough

Input: nums: [1,1,1,2,2,3], k=2

Goal: Find the 2 numbers that appear most frequently

Step 1: Count frequency of each number

{1:3, 2:2, 3:1}

Why: We need to know how often each number appears to find the most frequent

Step 2: Add (1,3) to min-heap

Heap: [(1,3)]

Why: Start building heap with first frequency

Step 3: Add (2,2) to min-heap

Heap: [(2,2), (1,3)]

Why: Add second frequency, heap size still less than k=2

Step 4: Add (3,1) to min-heap, then remove smallest frequency

Heap before removal: [(3,1), (1,3), (2,2)]
Heap after removal: [(2,2), (1,3)]

Why: Heap size exceeded k=2, remove least frequent (3,1) to keep top 2

Result:

Heap contains [(2,2), (1,3)] -> top 2 frequent elements are 1 and 2

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> freq;
    for (int num : nums) {
        freq[num]++;
    }

    // Min-heap to keep top k frequent elements
    auto cmp = [](const pair<int,int>& a, const pair<int,int>& b) { return a.second > b.second; };
    priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> minHeap(cmp);

    for (auto& [num, count] : freq) {
        minHeap.push({num, count});
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }

    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().first);
        minHeap.pop();
    }
    return result;
}

int main() {
    vector<int> nums = {1,1,1,2,2,3};
    int k = 2;
    vector<int> topK = topKFrequent(nums, k);
    for (int num : topK) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

for (int num : nums) { freq[num]++; }

Count frequency of each number in the input list

auto cmp = [](pair<int,int>& a, pair<int,int>& b) { return a.second > b.second; };

Define comparison to create min-heap based on frequency

for (auto& [num, count] : freq) { minHeap.push({num, count}); if (minHeap.size() > k) { minHeap.pop(); } }

Add each number-frequency pair to min-heap and remove least frequent if heap size exceeds k

while (!minHeap.empty()) { result.push_back(minHeap.top().first); minHeap.pop(); }

Extract top k frequent elements from heap into result

Output

2 1 

Complexity Analysis

Time: O(n log k) because we count frequencies in O(n) and maintain a heap of size k for n unique elements

Space: O(n) for the frequency map and heap storing up to k elements

vs Alternative: Using sorting all frequencies would be O(n log n), which is slower than heap approach for large n and small k

Edge Cases

Empty input list

Returns empty list since no elements to count

DSA C++

for (int num : nums) { freq[num]++; }

k equals number of unique elements

Returns all unique elements since heap never exceeds size k

DSA C++

if (minHeap.size() > k) { minHeap.pop(); }

All elements have same frequency

Returns any k elements since frequencies tie, heap keeps last k inserted

DSA C++

minHeap.push({num, count});

When to Use This Pattern

When asked to find the top K frequent items efficiently, use a frequency map combined with a min-heap of size K to keep track of the most frequent elements.

Common Mistakes

Mistake: Using a max-heap for all elements and then popping k times, which uses more memory and time
Fix: Use a min-heap of size k to keep only top k elements, popping the smallest frequency when size exceeds k

Mistake: Not counting frequencies correctly before building the heap
Fix: First build a frequency map by iterating over all elements

Summary

Find the k most frequent elements by counting and using a min-heap to keep top k.

Use when you need the most frequent items efficiently without sorting all elements.

Keep a small heap that removes the least frequent element to maintain only top k.