package main import ( "container/heap" "fmt" ) type Element struct { value int freq int } type MinHeap []Element func (h MinHeap) Len() int { return len(h) } func (h MinHeap) Less(i, j int) bool { return h[i].freq < h[j].freq } 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.(Element)) } func (h *MinHeap) Pop() interface{} { n := len(*h) el := (*h)[n-1] *h = (*h)[:n-1] return el } 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, Element{val, freq}) if h.Len() > k { heap.Pop(h) } } res := make([]int, 0, k) for h.Len() > 0 { res = append(res, heap.Pop(h).(Element).value) } return res } func main() { nums := []int{1,1,1,2,2,3} k := 2 result := topKFrequent(nums, k) fmt.Println(result) }
The min-heap keeps the top k frequent elements by frequency. When popping from the heap, elements with smaller frequency come out first. So the result slice is built from least frequent of the top k to most frequent. For the input, frequencies are: 1->3, 2->2, 3->1. The top 2 frequent are 1 and 2. Popping from heap returns 2 first, then 1, so output is [2, 1].
A min-heap keeps the smallest frequency element at the top. When the heap size exceeds k, we remove the smallest frequency element. This way, after processing all elements, the heap contains the k elements with the highest frequencies. Using a max-heap would require storing all elements and then extracting k largest, which is less efficient.
type MinHeap []Element func (h MinHeap) Len() int { return len(h) } func (h MinHeap) Less(i, j int) bool { return h[i].freq > h[j].freq } func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
The Less method returns true if h[i].freq > h[j].freq, which makes the heap a max-heap (largest frequency at top). This breaks the logic expecting a min-heap to remove smallest frequency elements first, leading to incorrect results.
package main import ( "container/heap" "fmt" ) type Element struct { value int freq int } type MinHeap []Element func (h MinHeap) Len() int { return len(h) } func (h MinHeap) Less(i, j int) bool { if h[i].freq == h[j].freq { return h[i].value > h[j].value } return h[i].freq < h[j].freq } 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.(Element)) } func (h *MinHeap) Pop() interface{} { n := len(*h) el := (*h)[n-1] *h = (*h)[:n-1] return el } 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, Element{val, freq}) if h.Len() > k { heap.Pop(h) } } res := make([]int, 0, k) for h.Len() > 0 { res = append(res, heap.Pop(h).(Element).value) } return res } func main() { nums := []int{4,4,1,1,2,2,3} k := 3 result := topKFrequent(nums, k) fmt.Println(result) }
The Less method breaks ties by comparing values in descending order (h[i].value > h[j].value). This means among equal frequencies, elements with larger value are popped first. Frequencies are: 4->2, 1->2, 2->2, 3->1. The top 3 frequent are 4,1,2. The heap pops the smallest frequency first, so 3 (freq 1) is popped last and not in top 3. The result after popping heap is [3, 2, 1].
Using a hash map to count frequencies is O(n). Maintaining a min-heap of fixed size k=5 while iterating over the frequency map keeps memory usage low and insertion/removal operations are O(log k). Sorting the entire list or using a max-heap of all unique elements is less efficient for large data. Balanced trees add overhead and are slower than heaps for this use case.