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

Top K Frequent Elements Using Heap

📖 Scenario: You are working on a music app that tracks how many times each song is played. You want to find the top k most played songs to show on the homepage.

🎯 Goal: Build a program that finds the top k frequent elements from a list of integers using a heap (priority queue).

📋 What You'll Learn

Create a list of integers called plays with exact values

Create an integer variable called k for the number of top frequent elements

Use a dictionary called frequencyMap to count frequencies

Use a min-heap (priority queue) to keep track of top k frequent elements

Print the top k frequent elements as a list

💡 Why This Matters

🌍 Real World

Finding the most popular items, songs, or products based on user activity is common in recommendation systems and dashboards.

💼 Career

This technique is useful for software engineers working on data analysis, backend services, and performance optimization.

1

Create the list of song plays

Create a list of integers called plays with these exact values: 1, 1, 1, 2, 2, 3

DSA C#

# Create the list called plays with the given values
# Your code here

Hint

Use List<int> and initialize it with the exact numbers inside curly braces.

2

Set the number of top frequent elements

Create an integer variable called k and set it to 2

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List plays = new List { 1, 1, 1, 2, 2, 3 };
        // Create variable k and set it to 2
        // Your code here
    }
}

Hint

Use int k = 2; to create the variable.

3

Count frequencies and find top k frequent elements using a heap

Create a dictionary called frequencyMap to count how many times each number appears in plays. Then use a PriorityQueue<int, int> called minHeap to keep the top k frequent elements by frequency. Add elements to minHeap and remove the smallest frequency when size exceeds k. Finally, create a list called topK and add elements from minHeap.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List plays = new List { 1, 1, 1, 2, 2, 3 };
        int k = 2;
        // Count frequencies in frequencyMap
        // Use minHeap to keep top k frequent elements
        // Extract top k elements into topK list
        // Your code here
    }
}

Hint

Use a dictionary to count frequencies. Use PriorityQueue<int, int> as a min-heap with frequency as priority. Keep heap size at most k. Extract elements and reverse the list.

4

Print the top k frequent elements

Print the list topK using Console.WriteLine with string.Join to show elements separated by spaces.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List plays = new List { 1, 1, 1, 2, 2, 3 };
        int k = 2;

        Dictionary frequencyMap = new Dictionary();
        foreach (int play in plays)
        {
            if (frequencyMap.ContainsKey(play))
                frequencyMap[play]++;
            else
                frequencyMap[play] = 1;
        }

        PriorityQueue minHeap = new PriorityQueue();
        foreach (var pair in frequencyMap)
        {
            minHeap.Enqueue(pair.Key, pair.Value);
            if (minHeap.Count > k)
                minHeap.Dequeue();
        }

        List topK = new List();
        while (minHeap.Count > 0)
        {
            topK.Add(minHeap.Dequeue());
        }

        topK.Reverse();

        // Print the topK list separated by spaces
        // Your code here
    }
}

Hint

Use Console.WriteLine(string.Join(" ", topK)); to print the elements separated by spaces.

Practice

1. What is the main purpose of using a heap in the Top K Frequent Elements problem?

easy

A. To store elements without any order

B. To sort all elements in ascending order

C. To efficiently keep track of the top K elements by frequency

D. To remove duplicates from the list

Solution

1. Step 1: Understand the role of a heap

   A heap is a special tree-based data structure that helps efficiently find and maintain the largest or smallest elements.

2. Step 2: Apply heap to the problem context

   In the Top K Frequent Elements problem, a heap helps keep track of the K elements with the highest frequency without sorting the entire list.

3. Final Answer:

   To efficiently keep track of the top K elements by frequency -> Option C

4. Quick Check:

   Heap = Efficient top K tracking [OK]

Hint: Heap keeps top K elements efficiently without full sorting [OK]

Common Mistakes:

• Thinking heap sorts all elements fully
• Confusing heap with simple list or array
• Ignoring frequency importance

2. Which of the following C# code snippets correctly declares a min-heap using SortedSet for integers?

easy

A. var minHeap = new Stack<int>();

B. var minHeap = new List<int>();

C. var minHeap = new Dictionary();

D. var minHeap = new SortedSet<int>();

Solution

1. Step 1: Identify data structure for min-heap

   A min-heap can be implemented using a SortedSet in C# because it keeps elements sorted automatically.

2. Step 2: Check code correctness

   var minHeap = new SortedSet<int>(); declares a SortedSet<int>, which acts like a min-heap by keeping smallest element accessible.

3. Final Answer:

   var minHeap = new SortedSet<int>(); -> Option D

4. Quick Check:

   SortedSet = min-heap structure [OK]

Hint: Use SortedSet for min-heap in C# [OK]

Common Mistakes:

• Using List instead of a heap structure
• Confusing Dictionary with heap
• Using Stack which is LIFO, not heap

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

int[] nums = {1,1,1,2,2,3};
int k = 2;
var freq = new Dictionary();
foreach(var num in nums) freq[num] = freq.GetValueOrDefault(num, 0) + 1;
var heap = new SortedSet<(int freq, int num)>();
foreach(var pair in freq) {
    heap.Add((pair.Value, pair.Key));
    if(heap.Count > k) heap.Remove(heap.Min);
}
var result = heap.Select(x => x.num).ToList();
Console.WriteLine(string.Join(", ", result));

medium

A. 2, 1

B. 1, 2

C. 1, 3

D. 3, 2

Solution

1. Step 1: Count frequencies

   Frequencies are: 1 -> 3 times, 2 -> 2 times, 3 -> 1 time.

2. Step 2: Use min-heap to keep top 2 frequent

   Heap keeps pairs (freq, num). It adds all pairs: (3,1), (2,2), (1,3). When size > 2, removes smallest freq (1,3). Leaving (2,2) and (3,1). SortedSet iterates in ascending order: (2,2), then (3,1).

3. Step 3: Output order

   Result list is created by selecting num from heap in ascending order of freq, so output is "2, 1".

4. Final Answer:

   2, 1 -> Option A

5. Quick Check:

   Top 2 frequent = 2, 1 [OK]

Hint: Keep heap size k, remove smallest freq when exceeded [OK]

Common Mistakes:

• Not removing smallest freq when heap size exceeds k
• Mixing element and frequency order
• Printing frequencies instead of elements

4. Identify the bug in this C# code snippet for top 1 frequent element:

int[] nums = {4,4,4,6,6,7};
int k = 1;
var freq = new Dictionary();
foreach(var num in nums) freq[num] = freq.GetValueOrDefault(num, 0) + 1;
var heap = new SortedSet<(int freq, int num)>();
foreach(var pair in freq) {
    heap.Add((pair.Value, pair.Key));
    if(heap.Count > k) heap.Remove(heap.Max);
}
var result = heap.Select(x => x.num).ToList();
Console.WriteLine(string.Join(", ", result));

medium

A. Removing heap.Max instead of heap.Min causes wrong elements removal

B. Dictionary initialization is incorrect

C. Using GetValueOrDefault causes runtime error

D. Heap should store only numbers, not frequency

Solution

1. Step 1: Understand heap removal logic

   Heap is a min-heap by frequency, so smallest freq is at Min, largest at Max.

2. Step 2: Identify incorrect removal

   Code removes heap.Max when size exceeds k, which removes the largest frequency element instead of smallest, causing wrong result.

3. Final Answer:

   Removing heap.Max instead of heap.Min causes wrong elements removal -> Option A

4. Quick Check:

   Remove heap.Min to keep top frequent [OK]

Hint: Remove heap.Min to keep top frequent elements [OK]

Common Mistakes:

• Removing heap.Max instead of heap.Min
• Confusing frequency and element order
• Not updating frequency dictionary correctly

5. Given the array nums = {5,3,1,1,1,3,73,1} and k = 2, which approach correctly returns the top 2 frequent elements using a heap in C#? A) Use a max-heap to store all elements and pop k times. B) Use a min-heap of size k to keep top frequent elements by frequency. C) Sort the array and pick last k elements. D) Use a queue to store elements and count frequencies later.

hard

A. Use a max-heap to store all elements and pop k times.

B. Use a min-heap of size k to keep top frequent elements by frequency.

C. Sort the array and pick last k elements.

D. Use a queue to store elements and count frequencies later.

Solution

1. Step 1: Understand frequency counting

   Count frequencies: 1 -> 4 times, 3 -> 2 times, 5 -> 1 time, 73 -> 1 time.

2. Step 2: Use min-heap of size k

   Use a min-heap to keep only top k frequent elements by frequency. When heap size exceeds k, remove smallest frequency element.

3. Step 3: Why other options fail

   A) Max-heap of all elements is inefficient. C) Sorting array doesn't group frequencies. D) Queue doesn't help frequency counting efficiently.

4. Final Answer:

   Use a min-heap of size k to keep top frequent elements by frequency. -> Option B

5. Quick Check:

   Min-heap size k = correct approach [OK]

Hint: Keep min-heap size k to track top frequent elements [OK]

Common Mistakes:

• Using max-heap for all elements wastes memory
• Sorting array ignores frequency counts
• Using queue without frequency map