Top K Frequent Elements Using Heap in DSA Go - 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 return those elements.

Execution Sample

DSA Go

nums := []int{1,1,1,2,2,3}
k := 2
// Count frequencies
// Use min-heap to keep top k
// Extract results

Find top 2 frequent elements from the list [1,1,1,2,2,3]

Execution Table

Step	Operation	Element	Frequency	Heap State (freq, elem)	Heap Size	Action
1	Count frequency	1	3	[]	0	Frequency map updated
2	Count frequency	2	2	[]	0	Frequency map updated
3	Count frequency	3	1	[]	0	Frequency map updated
4	Push to heap	1	3	[(3,1)]	1	Heap size < k, push
5	Push to heap	2	2	[(2,2),(3,1)]	2	Heap size < k, push
6	Compare freq with min in heap	3	1	[(2,2),(3,1)]	2	1 < 2? Yes, no push
7	Extract elements	-	-	[(2,2),(3,1)]	2	Return elements 1 and 2

💡 All elements processed, heap contains top 2 frequent elements

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
frequency_map	{}	{1:3}	{1:3, 2:2}	{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}
heap	[]	[]	[]	[]	[(3,1)]	[(2,2),(3,1)]	[(2,2),(3,1)]	[(2,2),(3,1)]
heap_size	0	0	0	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?

Using a min-heap of size k keeps the smallest frequency at the top, so when a new element with higher frequency comes, we can easily remove the smallest and keep only top k. See step 6 in execution_table where element with freq 1 is ignored because it's less than min freq 2 in heap.

What happens if the heap size is less than k when adding elements?

We simply push the new element into the heap without removing anything. This is shown in steps 4 and 5 where heap size grows until it reaches k.

Why do we compare the current element's frequency with the min frequency in the heap?

Because the heap keeps the smallest frequency on top, if current frequency is bigger, it means this element is more frequent and should replace the smallest in heap. This is shown in step 6.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the heap size after pushing element 2?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Heap Size' column at step 5 in execution_table

At which step does the algorithm decide not to push element 3 into the heap?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'Action' column in execution_table where it says 'No push'

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

A Heap would contain [(1,3),(2,2),(3,1)]

B Heap would contain [(3,1),(2,2)]

C Heap would contain [(3,1),(2,2),(1,3),(4,4)]

D Heap would be empty

💡 Hint

With k=3, heap can hold all three elements, see variable_tracker for heap states

Concept Snapshot

Top K Frequent Elements Using Heap:
- Count frequencies of elements
- Use a min-heap of size k to keep top k frequent
- Push elements until heap size k
- If new freq > min freq in heap, replace min
- Extract elements from heap as result

Full Transcript

This visualization shows how to find the top K frequent elements using a min-heap. First, we count how many times each element appears. Then, we build a min-heap that holds at most k elements. For each element frequency, if the heap is not full, we push it. If the heap is full and the current frequency is bigger than the smallest frequency in the heap, we remove the smallest and add the current one. After processing all elements, the heap contains the top k frequent elements. The execution table tracks each step, showing heap state and actions. The variable tracker shows how frequency map and heap change over time. Key moments clarify why a min-heap is used and how elements are pushed or skipped. The quiz tests understanding of heap size, decision steps, and effect of changing k.