Top K Frequent Elements Using Heap in DSA C#

Mental Model

Find the elements that appear most often by counting them, then keep only the top K using a special list that quickly removes the least frequent.

Analogy: Imagine you have a bag of colored balls and want to find the top K colors that appear most. You count each color, then keep only the K colors with the most balls by always removing the color with the fewest balls when you add a new one.

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]
Top K frequent elements: 1, 2

Dry Run Walkthrough

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

Goal: Find the 2 elements that appear most frequently in the array

Step 1: Count frequency of each element

{1:3, 2:2, 3:1}

Why: We need to know how often each element appears to find the most frequent

Step 2: Add element 1 with frequency 3 to the min-heap

Min-heap: [(1,3)]

Why: Start building the heap with the first element and its frequency

Step 3: Add element 2 with frequency 2 to the min-heap

Min-heap: [(2,2), (1,3)]

Why: Add second element; heap keeps smallest frequency on top

Step 4: Add element 3 with frequency 1; since heap size > k, remove smallest frequency element

Min-heap after removal: [(1,3), (2,2)]

Why: Keep heap size at k by removing the element with lowest frequency (3,1) is removed

Result:

Min-heap: [(1,3), (2,2)]
Top 2 frequent elements: 1, 2

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Solution {
    public IList<int> TopKFrequent(int[] nums, int k) {
        // Count frequency of each element
        Dictionary<int, int> freqMap = new Dictionary<int, int>();
        foreach (int num in nums) {
            freqMap[num] = freqMap.TryGetValue(num, out int count) ? count + 1 : 1;
        }

        // Min-heap to keep top k frequent elements
        PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();

        foreach (var pair in freqMap) {
            minHeap.Enqueue(pair.Key, pair.Value); // enqueue element with frequency as priority
            if (minHeap.Count > k) {
                minHeap.Dequeue(); // remove element with smallest frequency
            }
        }

        // Extract elements from heap
        List<int> result = new List<int>();
        while (minHeap.Count > 0) {
            result.Add(minHeap.Dequeue());
        }

        result.Reverse(); // highest frequency first
        return result;
    }

    static void Main() {
        Solution sol = new Solution();
        int[] nums = {1,1,1,2,2,3};
        int k = 2;
        IList<int> topK = sol.TopKFrequent(nums, k);
        Console.WriteLine(string.Join(", ", topK));
    }
}

freqMap[num] = freqMap.TryGetValue(num, out int count) ? count + 1 : 1;

count frequency of each element in the array

minHeap.Enqueue(pair.Key, pair.Value);

add element to min-heap with frequency as priority

if (minHeap.Count > k) { minHeap.Dequeue(); }

keep heap size at k by removing element with smallest frequency

while (minHeap.Count > 0) { result.Add(minHeap.Dequeue()); }

extract elements from heap to get top k frequent elements

result.Reverse();

reverse to have highest frequency 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 for n unique elements

Space: O(n) for the frequency map and heap storing up to k elements

vs Alternative: Using sorting all frequencies would be O(n log n), so heap reduces time when k is much smaller than n

Edge Cases

empty array

returns empty list since no elements exist

DSA C#

foreach (int num in nums) { ... } handles empty input by no iterations

k equals number of unique elements

returns all unique elements sorted by frequency

DSA C#

if (minHeap.Count > k) { minHeap.Dequeue(); } ensures heap size does not exceed k

all elements have same frequency

returns any k elements since frequencies tie

DSA C#

minHeap.Enqueue(pair.Key, pair.Value); maintains heap order by frequency

When to Use This Pattern

When asked to find the top K frequent items in a collection, use a frequency map plus a min-heap to efficiently track the K largest frequencies.

Common Mistakes

Mistake: Using a max-heap and extracting all elements instead of a min-heap to keep only top K
Fix: Use a min-heap of size k to discard smaller frequencies early and keep only top K

Mistake: Not reversing the result after extracting from min-heap, resulting in ascending frequency order
Fix: Reverse the extracted list to get descending order of frequency

Summary

Find the K elements that appear most frequently using a frequency map and a min-heap.

Use when you need the top K frequent elements efficiently without sorting all elements.

Keep a min-heap of size K to discard less frequent elements and keep only the top K.

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