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.

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 keep track of 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 tracking

   A heap helps keep track of elements based on their frequency efficiently, especially when we want only the top K frequent elements.

2. Step 2: Compare with other options

   Sorting all elements or removing duplicates is not the main goal here; the heap is used for efficient frequency comparison and retrieval.

3. Final Answer:

   To efficiently find and keep track of the top K frequent elements -> Option A

4. Quick Check:

   Heap usage = Efficient top K tracking [OK]

Hint: Heap keeps top K frequent elements efficiently [OK]

Common Mistakes:

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

2. Which of the following Go code snippets correctly initializes a min-heap to store pairs of (frequency, element) for the top K frequent elements problem?

easy

A. heap := new([]int); heap.Init(heap)

B. heap := make([]int, 0); heap.Push(heap, pair)

C. heap := &IntHeap{}; heap.Init(heap)

D. var h IntHeap; heap.Init(&h)

Solution

1. Step 1: Understand Go heap initialization

   In Go, a heap is usually implemented by defining a type that implements heap.Interface, then initializing it with heap.Init(&heap).

2. Step 2: Analyze options

   var h IntHeap; heap.Init(&h) correctly declares a variable of type IntHeap and initializes it by passing its address to heap.Init. Other options misuse pointers or heap methods.

3. Final Answer:

   var h IntHeap; heap.Init(&h) -> Option D

4. Quick Check:

   Correct heap init = var h IntHeap; heap.Init(&h) [OK]

Hint: Use heap.Init with pointer to heap variable [OK]

Common Mistakes:

• Calling heap.Init on non-pointer
• Using make for heap without type
• Incorrect pointer usage with new([]int)

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

nums := []int{1,1,1,2,2,3}
result := topKFrequent(nums, 2)
fmt.Println(result)

Assuming topKFrequent is correctly implemented using a min-heap.

medium

A. [1, 3]

B. [2, 3]

C. [1, 2]

D. [3, 2]

Solution

1. Step 1: Count frequencies of elements

   1 appears 3 times, 2 appears 2 times, 3 appears 1 time.

2. Step 2: Extract top 2 frequent elements

   The top 2 frequent elements are 1 (3 times) and 2 (2 times). So the result is [1, 2].

3. Final Answer:

   [1, 2] -> Option C

4. Quick Check:

   Top 2 frequent = [1, 2] [OK]

Hint: Count frequencies, pick top K by frequency [OK]

Common Mistakes:

• Confusing element order in output
• Including less frequent elements
• Ignoring frequency counts

4. The following Go code snippet is intended to find the top 3 frequent elements but has a bug. What is the bug?

func topKFrequent(nums []int, k int) []int {
    freqMap := make(map[int]int)
    for _, num := range nums {
        freqMap[num]++
    }
    
    h := &IntHeap{}
    heap.Init(h)
    
    for num, freq := range freqMap {
        heap.Push(h, Pair{freq, num})
        if h.Len() > k {
            heap.Pop(h)
        }
    }
    
    res := make([]int, 0, k)
    for h.Len() > 0 {
        p := heap.Pop(h).(Pair)
        res = append(res, p.num)
    }
    return res
}

medium

A. Result list is in ascending frequency order, needs reversing

B. Heap is not initialized before use

C. Frequency map is not counting correctly

D. Heap size check should be < k, not > k

Solution

1. Step 1: Understand heap usage and result order

   The min-heap keeps smallest frequency on top, so popping elements gives ascending frequency order.

2. Step 2: Identify output order issue

   Appending popped elements directly results in ascending order, but top K frequent elements should be in descending order of frequency.

3. Final Answer:

   Result list is in ascending frequency order, needs reversing -> Option A

4. Quick Check:

   Output order issue = Result list is in ascending frequency order, needs reversing [OK]

Hint: Pop from min-heap gives ascending order; reverse result [OK]

Common Mistakes:

• Ignoring output order of popped elements
• Not initializing heap properly
• Incorrect frequency counting

5. Given a large list of integers where many elements have the same frequency, how should the Top K Frequent Elements Using Heap algorithm be adapted to return the top K elements sorted by frequency and then by element value ascending when frequencies tie?

hard

A. Use a map only without heap to track frequencies

B. Use a heap with custom comparison: first by frequency, then by element value ascending

C. Use a max-heap with frequency only, ignoring element value

D. Sort the entire list first, then pick first K elements

Solution

1. Step 1: Understand tie-breaking requirement

   When frequencies tie, elements should be ordered by their value ascending to maintain consistent order.

2. Step 2: Adapt heap comparison logic

   Implement a custom comparison in the heap that compares frequency first, and if equal, compares element values ascending.

3. Final Answer:

   Use a heap with custom comparison: first by frequency, then by element value ascending -> Option B

4. Quick Check:

   Custom heap comparison handles ties correctly [OK]

Hint: Add tie-breaker in heap comparison for stable ordering [OK]

Common Mistakes:

• Ignoring tie-breaker in heap comparison
• Sorting entire list unnecessarily
• Using max-heap without tie-break logic