Top K Frequent Elements Using Heap in DSA Go

Mental Model

Find the most common items by counting them, then keep only the top few using a special list that quickly removes the least common.

Analogy: Imagine you have a basket of fruits and want to keep only the top 2 most frequent fruits. You count each fruit, then keep adding fruits to a small box that always throws out the least common fruit when full.

Input array: [1,1,1,2,2,3]
Frequency map: {1:3, 2:2, 3:1}
Min-heap (size k=2):
  [2:2]
  [1:3]
Heap keeps smallest frequency on top to remove when new bigger frequency comes.

Dry Run Walkthrough

Input: nums: [1,1,1,2,2,3], k=2

Goal: Find the 2 most frequent elements in the list

Step 1: Count frequency of each number

Frequency map: {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 keeps smallest frequency on top

Step 4: Add (3,1) to min-heap; since heap size > k, remove smallest frequency

Heap before removal: [(3,1), (1,3), (2,2)]
Heap after removal: [(2,2), (1,3)]

Why: Keep heap size at k=2 by removing least frequent element

Step 5: Extract elements from heap as result

Result: [1, 2]

Why: These are the top 2 frequent elements

Result:

Heap final state: [(2,2), (1,3)]
Top 2 frequent elements: [1, 2]

Annotated Code

DSA Go

package main

import (
	"container/heap"
	"fmt"
)

// Item holds number and its frequency
type Item struct {
	value    int
	priority int
}

// MinHeap implements heap.Interface for Items based on priority
type MinHeap []Item

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].priority < h[j].priority }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(Item))
}

func (h *MinHeap) Pop() interface{} {
	n := len(*h)
	item := (*h)[n-1]
	*h = (*h)[:n-1]
	return item
}

func topKFrequent(nums []int, k int) []int {
	freqMap := make(map[int]int)
	for _, num := range nums {
		freqMap[num]++
	}

	h := &MinHeap{}
	heap.Init(h)

	for val, freq := range freqMap {
		heap.Push(h, Item{value: val, priority: freq})
		if h.Len() > k {
			heap.Pop(h) // remove least frequent
		}
	}

	result := make([]int, 0, k)
	for h.Len() > 0 {
		item := heap.Pop(h).(Item)
		result = append(result, item.value)
	}

	// reverse result because heap pops smallest first
	for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
		result[i], result[j] = result[j], result[i]
	}

	return result
}

func main() {
	nums := []int{1, 1, 1, 2, 2, 3}
	k := 2
	res := topKFrequent(nums, k)
	fmt.Println(res)
}

freqMap := make(map[int]int) for _, num := range nums { freqMap[num]++ }

Count frequency of each number in input

h := &MinHeap{} heap.Init(h)

Initialize empty min-heap to store top k frequent elements

for val, freq := range freqMap { heap.Push(h, Item{value: val, priority: freq}) if h.Len() > k { heap.Pop(h) // remove least frequent } }

Add each frequency to heap; keep heap size at k by removing smallest frequency

for h.Len() > 0 { item := heap.Pop(h).(Item) result = append(result, item.value) }

Extract elements from heap to build result list

for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 { result[i], result[j] = result[j], result[i] }

Reverse result to have most frequent elements first

Output

[1 2]

Complexity Analysis

Time: O(n log k) because we count frequencies in O(n) and maintain a heap of size k with O(log k) operations for each unique element

Space: O(n) for frequency map and heap storage in worst case when all elements are unique

vs Alternative: Compared to sorting all frequencies O(n log n), using a heap reduces time to O(n log k) which is faster when k is much smaller than n

Edge Cases

Empty input array

Returns empty list since no elements to process

DSA Go

freqMap := make(map[int]int)
for _, num := range nums {
	freqMap[num]++
}

k equals number of unique elements

Returns all unique elements sorted by frequency

DSA Go

if h.Len() > k {
	heap.Pop(h) // remove least frequent
}

All elements have same frequency

Returns any k elements since frequencies tie

DSA Go

heap.Push and heap.Pop maintain heap size and order

When to Use This Pattern

When asked to find the top k frequent items efficiently, use a min-heap to keep track of the k largest frequencies without sorting all elements.

Common Mistakes

Mistake: Using a max-heap and popping k times instead of maintaining a min-heap of size k
Fix: Use a min-heap to keep only k elements, popping the smallest frequency when size exceeds k

Mistake: Not reversing the result after popping from min-heap, resulting in least frequent first
Fix: Reverse the result list after extracting from heap to get most frequent first

Summary

Find the k most frequent elements by counting and using a min-heap to keep top k frequencies.

Use when you need the most common items efficiently without sorting all frequencies.

Keep a small heap of size k that always removes the least frequent to maintain top 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