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.

Practice

1. What is the main purpose of using a heap in the Top K Frequent Elements problem?

easy

A. To efficiently keep track of the top k elements by frequency

B. To sort all elements in ascending order

C. To store elements without any order

D. To remove duplicates from the list

Solution

1. Step 1: Understand the problem goal

   The problem requires finding the k elements that appear most frequently.

2. Step 2: Role of heap in this context

   A heap helps efficiently keep track of the top k frequent elements by maintaining a structure where the smallest frequency is easily accessible and can be replaced if a more frequent element is found.

3. Final Answer:

   To efficiently keep track of the top k elements by frequency -> Option A

4. Quick Check:

   Heap = Efficient top k tracking [OK]

Hint: Heap keeps smallest frequency on top for quick replacement [OK]

Common Mistakes:

• Thinking heap sorts all elements fully
• Confusing heap with simple array storage
• Assuming heap removes duplicates

2. Which of the following C++ STL containers is best suited to implement a min-heap for the Top K Frequent Elements problem?

easy

A. std::vector with std::make_heap and std::pop_heap

B. std::list

C. std::map

D. std::queue

Solution

1. Step 1: Identify heap implementation in C++ STL

   C++ STL uses a vector with heap algorithms like std::make_heap, std::pop_heap, and std::push_heap to implement heaps.

2. Step 2: Check other container suitability

   std::list and std::queue do not support heap operations directly. std::map is a balanced tree, not a heap.

3. Final Answer:

   std::vector with std::make_heap and std::pop_heap -> Option A

4. Quick Check:

   Vector + heap algorithms = min-heap [OK]

Hint: Use vector + heap functions for heap in C++ [OK]

Common Mistakes:

• Choosing std::map thinking it is a heap
• Using std::queue which is FIFO, not heap
• Using std::list which lacks random access

3. What is the output of the following C++ code snippet for nums = {1,1,1,2,2,3} and k = 2?

std::vector<int> nums = {1,1,1,2,2,3};
int k = 2;
// Frequency map
std::unordered_map freq;
for (int n : nums) freq[n]++;

// Min heap to store pairs (frequency, element)
std::priority_queue, std::vector>, std::greater<>> minHeap;

for (auto& p : freq) {
    minHeap.push({p.second, p.first});
    if (minHeap.size() > k) minHeap.pop();
}

std::vector<int> result;
while (!minHeap.empty()) {
    result.push_back(minHeap.top().second);
    minHeap.pop();
}
std::reverse(result.begin(), result.end());
for (int x : result) std::cout << x << " ";

medium

A. 3 2

B. 2 3

C. 1 3

D. 1 2

Solution

1. Step 1: Calculate frequencies

   Frequencies: 1 -> 3 times, 2 -> 2 times, 3 -> 1 time.

2. Step 2: Use min heap to keep top 2 frequent elements

   Insert (3,1), (2,2), (1,3). When size exceeds 2, pop smallest frequency. After all insertions, heap contains (2,2) and (3,1).

3. Step 3: Extract and reverse result

   Extracting gives elements 2 and 1, reversed to 1 2.

4. Final Answer:

   1 2 -> Option D

5. Quick Check:

   Top 2 frequent = 1 and 2 [OK]

Hint: Heap keeps smallest freq; pop when size > k [OK]

Common Mistakes:

• Not reversing the result vector
• Confusing element and frequency in pairs
• Popping wrong element from heap

4. Identify the bug in this code snippet for finding top k frequent elements:

std::unordered_map freq;
for (int n : nums) freq[n]++;

std::priority_queue> maxHeap;
for (auto& p : freq) {
    maxHeap.push({p.second, p.first});
    if (maxHeap.size() > k) maxHeap.pop();
}

std::vector<int> result;
while (!maxHeap.empty()) {
    result.push_back(maxHeap.top().second);
    maxHeap.pop();
}

medium

A. Frequency map is not created correctly

B. Using maxHeap and popping when size > k removes most frequent elements

C. Result vector is not reversed before output

D. Priority queue should store only elements, not pairs

Solution

1. Step 1: Understand heap type and popping logic

   maxHeap stores pairs with highest frequency on top. Popping when size > k removes the top (most frequent) element, which is wrong.

2. Step 2: Correct approach

   Use a minHeap to keep smallest frequency on top and pop it when size > k, so top k frequent remain.

3. Final Answer:

   Using maxHeap and popping when size > k removes most frequent elements -> Option B

4. Quick Check:

   MaxHeap pop removes top freq, wrong for top k [OK]

Hint: Pop from minHeap, not maxHeap, to keep top k [OK]

Common Mistakes:

• Using maxHeap and popping top element
• Not reversing result vector if needed
• Ignoring frequency-element pair structure

5. Given a large input array with many elements having the same frequency, how can you modify the heap approach to ensure the Top K Frequent Elements always returns the smallest elements when frequencies tie? Choose the best approach.

hard

A. Use a hash map only without any heap

B. Use a max-heap ordered by frequency only

C. Use a min-heap ordered by frequency, then by element value descending

D. Sort the entire array before building the heap

Solution

1. Step 1: Understand tie-breaking requirement

   When frequencies tie, we want the smaller element to come first in the top k.

2. Step 2: Modify heap ordering

   Use a min-heap that orders pairs by frequency first, then by element value ascending to break ties correctly.

3. Step 3: Why other options fail

   Max-heap ignores tie-break order, sorting entire array is inefficient, and hash map alone cannot find top k efficiently.

4. Final Answer:

   Use a min-heap ordered by frequency, then by element value ascending -> Option C

5. Quick Check:

   Min-heap with tie-break by element value [OK]

Hint: Tie-break by element value in heap comparator [OK]

Common Mistakes:

• Ignoring tie-break condition in heap
• Sorting entire array wastes time
• Using hash map alone without heap