Top K Frequent Elements Using Heap in DSA Rust

Mental Model

We want to find the K numbers that appear most often in a list by counting frequencies and keeping only the top K using a special list that quickly gives the smallest frequency.

Analogy: Imagine you have a bag of colored balls and want to keep only the K colors you see most often. You count how many balls of each color you have, then keep a small box that always holds the K colors with the most balls, throwing out less frequent colors as you find more frequent ones.

Input list: [1,1,1,2,2,3]
Frequency map: 1:3, 2:2, 3:1
Min-heap (size K=2):
[ (2,2) ]
 ↑ root (smallest frequency)
After adding (1,3):
[ (2,2), (1,3) ]
 ↑ root
We keep only top 2 frequent elements

Dry Run Walkthrough

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

Goal: Find the 2 numbers that appear most frequently 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 ones

Step 2: Add (1,3) to empty min-heap

Min-heap: [ (1,3) ]

Why: Start building heap with first frequency

Step 3: Add (2,2) to min-heap

Min-heap: [ (2,2), (1,3) ]
root is (2,2) because 2 < 3

Why: Keep heap size ≤ k=2, smallest frequency at root

Step 4: Add (3,1) to min-heap, but size exceeds k

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

Why: We must remove smallest frequency to keep only top k

Step 5: Remove root (3,1) from min-heap

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

Why: Remove least frequent element to keep top k frequent

Result:

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

Annotated Code

DSA Rust

use std::collections::{HashMap, BinaryHeap};
use std::cmp::Reverse;

fn top_k_frequent(nums: Vec<i32>, k: usize) -> Vec<i32> {
    let mut freq_map = HashMap::new();
    // Count frequency of each number
    for num in nums {
        *freq_map.entry(num).or_insert(0) += 1;
    }

    // Min-heap to keep top k frequent elements
    let mut heap = BinaryHeap::new();

    for (&num, &count) in freq_map.iter() {
        // Push Reverse to make min-heap by frequency
        heap.push(Reverse((count, num)));
        // If heap size exceeds k, pop smallest frequency
        if heap.len() > k {
            heap.pop();
        }
    }

    // Extract numbers from heap
    let mut result = Vec::with_capacity(k);
    while let Some(Reverse((_count, num))) = heap.pop() {
        result.push(num);
    }
    result.reverse(); // To have highest frequency first
    result
}

fn main() {
    let nums = vec![1,1,1,2,2,3];
    let k = 2;
    let top_k = top_k_frequent(nums, k);
    for num in top_k {
        print!("{} ", num);
    }
    println!();
}

*freq_map.entry(num).or_insert(0) += 1;

Count frequency of each number in the list

heap.push(Reverse((count, num)));

Add frequency and number as Reverse tuple to min-heap

if heap.len() > k { heap.pop(); }

Keep heap size at most k by removing smallest frequency

while let Some(Reverse((_count, num))) = heap.pop() { result.push(num); }

Extract numbers from heap to result vector

result.reverse();

Reverse result to have highest frequency 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 all unique elements

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

vs Alternative: A naive approach sorting all frequencies would be O(n log n), so using a heap reduces sorting cost to O(n log k)

Edge Cases

Empty input list

Returns empty list as no elements to process

DSA Rust

for num in nums { ... } handles empty by no iteration

k is zero

Returns empty list immediately as no top elements requested

DSA Rust

if heap.len() > k { heap.pop(); } prevents adding when k=0

All elements are the same

Returns that element as top frequent regardless of k

DSA Rust

*freq_map.entry(num).or_insert(0) += 1;

When to Use This Pattern

When asked to find the top K frequent items efficiently, use a frequency map combined with a min-heap to keep track of only the top K elements by frequency.

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 of size K to keep only top K frequent elements, popping smallest frequency when size exceeds K

Mistake: Not reversing the result after popping from heap, resulting in ascending frequency order
Fix: Reverse the result vector before returning to have highest frequency elements first

Summary

Finds the K most frequent elements in a list using a frequency map and a min-heap.

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

Keep a min-heap of size K to track top frequencies, removing smaller ones as you go.

Practice

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

easy

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

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 problem goal

   The goal is to find the K elements that appear most frequently in a list.

2. Step 2: Role of heap in this context

   A heap helps efficiently keep track of the top K frequent elements by maintaining a small structure that updates as we process frequencies.

3. Final Answer:

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

4. Quick Check:

   Heap = Efficient top K tracking [OK]

Hint: Heap keeps top K elements efficiently by frequency [OK]

Common Mistakes:

• Thinking heap sorts all elements fully
• Confusing heap with simple list storage
• Assuming heap removes duplicates

2. Which Rust data structure is best suited to store frequencies of elements before using a heap?

easy

A. Vec<T>

B. HashMap

C. LinkedList<T>

D. BinaryHeap<T>

Solution

1. Step 1: Identify frequency storage needs

   We need to count how many times each element appears, so we need a key-value structure.

2. Step 2: Choose appropriate Rust structure

   HashMap stores elements as keys and their counts as values efficiently.

3. Final Answer:

   HashMap<T, usize> -> Option B

4. Quick Check:

   Frequency storage = HashMap [OK]

Hint: Use HashMap to count frequencies before heap [OK]

Common Mistakes:

• Using Vec which is not key-value
• Using LinkedList which is inefficient here
• Confusing BinaryHeap with frequency map

3. What is the output of this Rust code snippet?

use std::collections::{BinaryHeap, HashMap};

fn top_k_frequent(nums: Vec<i32>, k: usize) -> Vec<i32> {
    let mut freq = HashMap::new();
    for num in nums {
        *freq.entry(num).or_insert(0) += 1;
    }
    let mut heap = BinaryHeap::new();
    for (&num, &count) in &freq {
        heap.push((count, num));
    }
    let mut result = Vec::new();
    for _ in 0..k {
        if let Some((_, num)) = heap.pop() {
            result.push(num);
        }
    }
    result
}

fn main() {
    let nums = vec![1,1,1,2,2,3];
    let k = 2;
    let top = top_k_frequent(nums, k);
    println!("{:?}", top);
}

medium

A. [2, 1]

B. [3, 2]

C. [1, 2]

D. [1, 3]

Solution

1. Step 1: Count frequencies

   1 appears 3 times, 2 appears 2 times, 3 appears 1 time.

2. Step 2: Push into max heap and pop top k

   Heap stores (count, num). Popping twice gives (3,1) then (2,2), so result is [1, 2].

3. Final Answer:

   [1, 2] -> Option C

4. Quick Check:

   Top 2 frequent = [1, 2] [OK]

Hint: Heap pops highest frequency first [OK]

Common Mistakes:

• Confusing order of output elements
• Ignoring frequency counts
• Assuming heap sorts by element value

4. Identify the bug in this Rust code for top K frequent elements:

use std::collections::{BinaryHeap, HashMap};

fn top_k_frequent(nums: Vec<i32>, k: usize) -> Vec<i32> {
    let mut freq = HashMap::new();
    for num in nums {
        freq.insert(num, freq.get(&num).unwrap_or(&0) + 1);
    }
    let mut heap = BinaryHeap::new();
    for (&num, &count) in &freq {
        heap.push((count, num));
    }
    let mut result = Vec::new();
    for _ in 0..k {
        if let Some((_, num)) = heap.pop() {
            result.push(num);
        }
    }
    result
}

medium

A. Using freq.insert overwrites counts incorrectly

B. BinaryHeap cannot store tuples

C. Loop range 0..k is invalid

D. Result vector is not returned

Solution

1. Step 1: Analyze frequency counting

   Using freq.insert(num, freq.get(&num).unwrap_or(&0) + 1) overwrites previous counts without incrementing properly.

2. Step 2: Correct frequency update method

   Should use *freq.entry(num).or_insert(0) += 1; to increment counts correctly.

3. Final Answer:

   Using freq.insert overwrites counts incorrectly -> Option A

4. Quick Check:

   Incorrect freq update = Bug [OK]

Hint: Use entry().or_insert() to increment counts safely [OK]

Common Mistakes:

• Using insert instead of entry for counting
• Assuming BinaryHeap can't store tuples
• Ignoring return of result vector

5. Given a large list with many elements having the same frequency, how can you modify the heap approach to ensure the top K frequent elements are returned in ascending order of their values when frequencies tie?

hard

A. Use a min-heap with (frequency, -element) pairs

B. Use a max-heap with (frequency, element) pairs and reverse result after extraction

C. Use a max-heap with (frequency, Reverse(element)) pairs

D. Use a max-heap with (frequency, element) pairs and sort result by element ascending after extraction

Solution

1. Step 1: Understand tie-breaking need

   When frequencies tie, elements should be ordered ascending by their value in final output.

2. Step 2: Heap stores by frequency only

   Heap orders by frequency, but does not guarantee order among ties, so sorting result after extraction is needed.

3. Step 3: Sort extracted top K by element ascending

   After popping top K from heap, sort the result vector by element ascending to meet tie-break condition.

4. Final Answer:

   Use a max-heap with (frequency, element) pairs and sort result by element ascending after extraction -> Option D

5. Quick Check:

   Sort after heap extraction for tie-break [OK]

Hint: Sort top K result by element ascending after heap extraction [OK]

Common Mistakes:

• Trying to encode tie-break in heap key incorrectly
• Using negative values causing confusion
• Not sorting result after extraction