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

Concept Flow - Top K Frequent Elements Using Heap

Count frequencies

↓

For each element frequency

↓

If heap size < k

↓

Else if frequency > min in heap

↓

Pop min

↓

After all elements processed

↓

Extract elements from heap → Result

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

Execution Sample

DSA C

int topKFrequent(int* nums, int numsSize, int k, int* returnSize) {
  // Count frequencies
  // Use min-heap of size k
  // Push/pop to keep top k
  // Extract results
  return NULL; // Placeholder return
}

This code finds the k most frequent elements using a min-heap.

Execution Table

Step	Operation	Element Processed	Heap Size	Heap Content (freq, elem)	Action
1	Count frequencies	nums = [1,1,1,2,2,3]	0	[]	Count: 1->3, 2->2, 3->1
2	Build heap	Start inserting frequencies	0	[]	Heap empty, start pushing
3	Push	Element 1 (freq 3)	1	[(3,1)]	Heap size < k=2, push (3,1)
4	Push	Element 2 (freq 2)	2	[(2,2),(3,1)]	Heap size < k=2, push (2,2)
5	Compare and Replace	Element 3 (freq 1)	2	[(2,2),(3,1)]	Freq 1 < min freq 2, skip
6	Extract	Final heap	2	[(2,2),(3,1)]	Extract elements: 2 and 1
7	Result	Top k elements	2	[1,2]	Return top 2 frequent elements

💡 All elements processed, heap contains top k frequent elements.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	Final
freq_map	{}	{1:3}	{1:3, 2:2}	{1:3, 2:2, 3:1}	{1:3, 2:2, 3:1}
heap	[]	[(3,1)]	[(2,2),(3,1)]	[(2,2),(3,1)]	[(2,2),(3,1)]
heap_size	0	1	2	2	2

Key Moments - 3 Insights

Why do we use a min-heap instead of a max-heap for top k frequent elements?

We keep the smallest frequency at the top to easily remove the least frequent element when the heap size exceeds k, as shown in step 5 where freq 1 is less than min freq 2 and is skipped.

What happens if the frequency of a new element is less than the smallest frequency in the heap?

We skip adding it to the heap to keep only the top k frequent elements, as in step 5 where element 3 with freq 1 is ignored.

How do we know when to stop adding elements to the heap?

Once all elements are processed and the heap size is k, we only add elements with frequency greater than the smallest in the heap, as shown in steps 4 and 5.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what is the heap content?

A [(3,1)]

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

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

D [(1,3)]

💡 Hint

Check the 'Heap Content' column at step 4 in the execution table.

At which step does the algorithm decide to skip adding an element to the heap?

A Step 5

B Step 4

C Step 3

D Step 6

💡 Hint

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

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

A 1

B 2

C 3

D 4

💡 Hint

Refer to the 'heap_size' variable in variable_tracker and imagine increasing k to 3.

Concept Snapshot

Top K Frequent Elements Using Heap:
- Count frequencies of all elements.
- Use a min-heap to keep top k frequent elements.
- Push elements until heap size is k.
- If new freq > min in heap, pop min and push new.
- Extract heap elements as result.
- Efficient for large data with limited k.

Full Transcript

This concept shows how to find the top k frequent elements using a min-heap. First, count how many times each element appears. Then, build a min-heap that holds at most k elements. For each element frequency, if the heap has less than k elements, push it in. If the heap is full and the new frequency is bigger than the smallest frequency in the heap, remove the smallest and add the new one. After processing all elements, the heap contains the top k frequent elements. Extract them to get the result. This method is efficient because it keeps only k elements in the heap, not all frequencies. The execution table shows each step with heap content and actions. The variable tracker shows how frequencies and heap size change. Key moments clarify why a min-heap is used and when elements are skipped. The quiz tests understanding of heap content and decisions during processing.

Practice

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

easy

A. To efficiently find and maintain the top K frequent elements

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 role of heap in frequency problems

   A heap helps keep track of the most frequent elements efficiently by allowing quick access to the smallest or largest frequency element.

2. Step 2: Identify why heap is used for top K elements

   Using a min-heap of size K allows us to maintain only the top K frequent elements, removing less frequent ones as we go.

3. Final Answer:

   To efficiently find and maintain the top K frequent elements -> Option A

4. Quick Check:

   Heap = Efficient top K tracking [OK]

Hint: Heap keeps top K elements efficiently by frequency [OK]

Common Mistakes:

• Thinking heap sorts all elements fully
• Using heap to remove duplicates
• Ignoring frequency counts in heap

2. Which of the following is the correct way to declare a min-heap in C++ using the standard library for storing pairs of (frequency, element)?

easy

A. priority_queue minHeap;

B. priority_queue> minHeap;

C. priority_queue, vector>, greater>> minHeap;

D. priority_queue, vector>, less>> minHeap;

Solution

1. Step 1: Understand C++ priority_queue syntax for min-heap

   By default, priority_queue is a max-heap. To make it min-heap, we use greater comparator.

2. Step 2: Check the correct template parameters

   We need a priority_queue of pairs, with vector as container, and greater> as comparator for min-heap.

3. Final Answer:

   priority_queue, vector>, greater>> minHeap; -> Option C

4. Quick Check:

   Min-heap = priority_queue with greater comparator [OK]

Hint: Use greater comparator for min-heap in priority_queue [OK]

Common Mistakes:

• Using default priority_queue which is max-heap
• Wrong comparator like less instead of greater
• Incorrect container type in priority_queue

3. What will be the output of the following code snippet that finds top 2 frequent elements?

#include 
#include 
#include 

int main() {
    int nums[] = {1,1,1,2,2,3};
    int freq[4] = {0};
    for(int i=0; i<6; i++) freq[nums[i]]++;
    int k = 2;
    int result[2];
    int idx = 0;
    for(int i=1; i<=3; i++) {
        if(idx < k) {
            result[idx++] = i;
        } else {
            int min_idx = 0;
            for(int j=1; j freq[result[min_idx]]) result[min_idx] = i;
        }
    }
    for(int i=0; i

medium

A. 3 2

B. 1 3

C. 2 3

D. 1 2

Solution

1. Step 1: Count frequencies of elements

   nums = {1,1,1,2,2,3} so freq[1]=3, freq[2]=2, freq[3]=1.

2. Step 2: Select top 2 frequent elements using simple logic

   Initially result = {1,2}. For i=3, freq[3]=1 is less than min freq in result (which is freq[2]=2), so no replacement.

3. Final Answer:

   1 2 -> Option D

4. Quick Check:

   Top 2 frequent = 1 and 2 [OK]

Hint: Count frequencies, keep top K by comparing min freq [OK]

Common Mistakes:

• Confusing element values with frequencies
• Replacing elements incorrectly in result array
• Ignoring initial filling of result array

4. Identify the bug in the following code snippet that tries to find top 3 frequent elements using a min-heap approach:

#include 
#include 
#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    vector<int> nums = {4,4,4,6,6,7,7,7,7};
    unordered_map freq;
    for(auto n : nums) freq[n]++;
    priority_queue, vector>, greater>> minHeap;
    int k = 3;
    for(auto it : freq) {
        minHeap.push({it.second, it.first});
        if(minHeap.size() > k) minHeap.pop();
    }
    while(!minHeap.empty()) {
        printf("%d ", minHeap.top().second);
        minHeap.pop();
    }
    return 0;
}

medium

A. The condition to pop from heap should be if size >= k, not > k

B. The output order is reversed; elements print from least to most frequent

C. The min-heap should store (element, frequency) pairs, not (frequency, element)

D. The frequency map is not initialized correctly

Solution

1. Step 1: Understand min-heap stores (frequency, element)

   Min-heap keeps smallest frequency on top, so popping prints from least to most frequent.

2. Step 2: Identify output order issue

   Printing while popping will print elements from lowest to highest frequency, not top frequent first.

3. Final Answer:

   The output order is reversed; elements print from least to most frequent -> Option B

4. Quick Check:

   Min-heap pop order = ascending frequency [OK]

Hint: Min-heap pops smallest first, so output order is reversed [OK]

Common Mistakes:

• Confusing pair order in heap
• Wrong pop condition for heap size
• Ignoring output order from heap pops

5. Given an array nums = {5,3,1,1,1,3,73,1} and k = 2, which approach correctly finds the top K frequent elements using a heap and handles ties properly?

hard

A. Use a min-heap of size k with (frequency, element) pairs, replacing when frequency is higher

B. Use a hash map only without any heap

C. Sort the array and pick the last k elements

D. Use a min-heap of (frequency, element) pairs and pop k times

Solution

1. Step 1: Count frequencies of elements

   Frequencies: 1->4, 3->2, 5->1, 73->1.

2. Step 2: Use min-heap of size k to keep top frequent elements

   Insert pairs (freq, element). If heap size exceeds k, pop smallest frequency. This keeps top k frequent elements efficiently.

3. Step 3: Handle ties by frequency naturally in heap

   Elements with same frequency are handled by heap order; ties do not break correctness.

4. Final Answer:

   Use a min-heap of size k with (frequency, element) pairs, replacing when frequency is higher -> Option A

5. Quick Check:

   Min-heap size k keeps top frequent elements [OK]

Hint: Min-heap size k keeps top frequent elements, replacing lower freq [OK]

Common Mistakes:

• Using max-heap and popping k times without size limit
• Sorting array instead of frequencies
• Ignoring heap for frequency tracking