Top K Frequent Elements Using Heap in DSA C++ - Execution Trace

Concept Flow - Top K Frequent Elements Using Heap

Count frequencies

→Build min-heap of size k

↓

For each element frequency

↓

If heap size < k

→Push element

↓

Else if current freq > min freq in heap

↓

Pop min freq

→Push current element

↓

After all elements processed

↓

Extract elements from heap

↓

Return top k frequent elements

Count how often each element appears, keep top k in a small heap, then extract them.

Execution Sample

DSA C++

vector<int> topKFrequent(vector<int>& nums, int k) {
  unordered_map<int,int> freq;
  for (int n : nums) freq[n]++;
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minHeap;
  for (auto& [num, count] : freq) {
    if (minHeap.size() < k) minHeap.push({count, num});
    else if (count > minHeap.top().first) {
      minHeap.pop();
      minHeap.push({count, num});
    }
  }
  vector<int> result;
  while (!minHeap.empty()) {
    result.push_back(minHeap.top().second);
    minHeap.pop();
  }
  return result;
}

Finds the k most frequent numbers in the input list using a min-heap.

Execution Table

Step	Operation	Frequency Map	Heap Content (count,num)	Heap Size	Visual Heap State
1	Count frequencies from nums=[1,1,1,2,2,3]	{1:3, 2:2, 3:1}	[]	0	Empty heap
2	Process element 1 with freq=3	{1:3, 2:2, 3:1}	[(3,1)]	1	Heap: (3,1)
3	Process element 2 with freq=2	{1:3, 2:2, 3:1}	[(2,2),(3,1)]	2	Heap: (2,2) root, (3,1) child
4	Process element 3 with freq=1	{1:3, 2:2, 3:1}	[(2,2),(3,1)]	2	Freq 1 < min heap root 2, skip
5	Extract elements from heap	{1:3, 2:2, 3:1}	[(2,2),(3,1)]	2	Heap before extraction
6	Pop (2,2) from heap	{1:3, 2:2, 3:1}	[(3,1)]	1	Heap after popping (2,2)
7	Pop (3,1) from heap	{1:3, 2:2, 3:1}	[]	0	Heap empty after popping (3,1)
8	Return result [2,1]	{1:3, 2:2, 3:1}	[]	0	Final top k frequent elements

💡 All elements processed and heap extracted to get top k frequent elements

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
freq	{}	{1:3,2:2,3:1}	{1:3,2:2,3:1}	{1:3,2:2,3:1}	{1:3,2:2,3:1}	{1:3,2:2,3:1}	{1:3,2:2,3:1}	{1:3,2:2,3:1}	{1:3,2:2,3:1}
minHeap	[]	[]	[(3,1)]	[(2,2),(3,1)]	[(2,2),(3,1)]	[(2,2),(3,1)]	[(3,1)]	[]	[]
result	[]	[]	[]	[]	[]	[]	[2]	[2,1]	[2,1]

Key Moments - 3 Insights

Why do we skip adding element 3 with frequency 1 to the heap?

Because the heap already has size k=2 and the smallest frequency in the heap is 2, which is greater than 1. So element 3 is less frequent and not included (see execution_table step 4).

Why do we use a min-heap instead of a max-heap?

A min-heap keeps the smallest frequency at the top, so when we find a more frequent element, we can remove the smallest frequency easily to keep only top k frequent elements (see concept_flow and execution_table steps 3-4).

How do we get the final top k elements from the heap?

We pop all elements from the min-heap after processing all frequencies, collecting their numbers into the result (see execution_table steps 5-8).

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the heap content?

A [(1,3),(2,2)]

B [(3,1)]

C [(2,2),(3,1)]

D []

💡 Hint

Check the 'Heap Content (count,num)' column at step 3 in execution_table

At which step does the heap skip adding an element due to lower frequency?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look for the step where the frequency is less than the min heap root in execution_table

If k was 3 instead of 2, how would the heap size change after processing all elements?

A Heap size would be 2

B Heap size would be 3

C Heap size would be 1

D Heap size would be 0

💡 Hint

Refer to variable_tracker row 'minHeap' and think about heap size relative to k

Concept Snapshot

Top K Frequent Elements Using Heap:
- Count frequencies of all elements
- Use a min-heap to keep top k frequent elements
- If heap size < k, push new element
- Else if new freq > min freq in heap, pop min and push new
- Extract elements from heap for result
- Efficient for large input with limited k

Full Transcript

This visualization shows how to find the top k frequent elements using a min-heap. First, we count how many times each number appears. Then, we build a min-heap that holds at most k elements with the highest frequencies. For each frequency, if the heap is not full, we add it. If it is full and the current frequency is bigger than the smallest in the heap, we remove the smallest and add the current one. After processing all, we pop all elements from the heap to get the top k frequent elements. The heap always keeps the smallest frequency on top to easily remove less frequent elements. This method is efficient and uses a small heap to track the top k frequencies.