Top K Frequent Elements Using Heap in DSA Go - Build from Scratch

Top K Frequent Elements Using Heap

📖 Scenario: You are working on a music app that wants to show the top k most played songs from a list of song plays. Each song is represented by an integer ID. Your task is to find the k songs that appear most frequently in the play history.

🎯 Goal: Build a program that finds the top k frequent elements from a list of integers using a heap data structure.

📋 What You'll Learn

Create a slice called plays with the exact values: []int{1,1,1,2,2,3}

Create an integer variable called k and set it to 2

Use a map called frequency to count how many times each song ID appears in plays

Use a min-heap to keep track of the top k frequent elements

Print the top k frequent elements as a slice

💡 Why This Matters

🌍 Real World

Finding the most frequent items is common in recommendation systems, search engines, and analytics dashboards.

💼 Career

Understanding heaps and frequency counting is important for software engineers working on performance-critical data processing and ranking algorithms.

1

Create the plays slice

Create a slice called plays with the exact values []int{1,1,1,2,2,3}.

DSA Go

# Create the plays slice with the given values
# Your code here

Hint

Use plays := []int{1,1,1,2,2,3} to create the slice.

2

Set the value of k

Create an integer variable called k and set it to 2.

DSA Go

package main

func main() {
    plays := []int{1,1,1,2,2,3}
    // Set k to 2
    // Your code here
}

Hint

Use k := 2 to create the variable.

3

Count frequencies and use a min-heap

Create a map called frequency to count how many times each song ID appears in plays. Then use a min-heap to keep track of the top k frequent elements. Use the container/heap package and define a heap type that stores pairs of (frequency, song ID).

DSA Go

package main

import (
    "container/heap"
    "fmt"
)

func main() {
    plays := []int{1,1,1,2,2,3}
    k := 2

    // Create frequency map
    // Your code here

    // Define and use min-heap to find top k frequent
    // Your code here
}

// Define a type for the heap
// Your code here

Hint

Use a map to count frequencies. Use a min-heap to keep only top k elements by frequency.

4

Print the top k frequent elements

Create a slice called result and pop all elements from the heap into it. Then print result.

DSA Go

package main

import (
    "container/heap"
    "fmt"
)

// Pair and MinHeap definitions
// ...

func main() {
    plays := []int{1,1,1,2,2,3}
    k := 2

    frequency := make(map[int]int)
    for _, song := range plays {
        frequency[song]++
    }

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

    for val, freq := range frequency {
        heap.Push(h, Pair{freq, val})
        if h.Len() > k {
            heap.Pop(h)
        }
    }

    // Pop all elements from heap into result slice
    // Print result slice
    // Your code here
}

Hint

Pop all elements from the heap and append their values to a slice. Then print the slice.