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

Top K Frequent Elements Using Heap

📖 Scenario: You are working on a data analysis tool that needs to find the most frequent items in a list of numbers. This helps in understanding which items appear the most often.

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

📋 What You'll Learn

Create a vector called nums with the exact values: [1, 1, 1, 2, 2, 3]

Create a variable called k and set it to 2

Use a HashMap called frequency_map to count the frequency of each number in nums

Use a BinaryHeap to find the top k frequent elements

Print the top k frequent elements as a vector

💡 Why This Matters

🌍 Real World

Finding the most frequent items is useful in data analysis, recommendation systems, and search engines to highlight popular content.

💼 Career

This technique is common in software engineering roles involving data processing, backend development, and algorithm design.

1

Create the initial list of numbers

Create a vector called nums with the exact values [1, 1, 1, 2, 2, 3].

DSA Rust

# Create the vector nums with the values [1, 1, 1, 2, 2, 3]
# Your code here

Hint

Use let nums = vec![1, 1, 1, 2, 2, 3]; to create the vector.

2

Add the variable for top K elements

Create a variable called k and set it to 2.

DSA Rust

fn main() {
    let nums = vec![1, 1, 1, 2, 2, 3];
    // Create variable k and set it to 2
    # Your code here
}

Hint

Use let k = 2; to create the variable.

3

Count frequencies and use a heap to find top K

Create a HashMap called frequency_map to count the frequency of each number in nums. Then use a BinaryHeap to find the top k frequent elements.

DSA Rust

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

fn main() {
    let nums = vec![1, 1, 1, 2, 2, 3];
    let k = 2;

    // Create frequency_map to count frequencies
    // Use BinaryHeap to find top k frequent elements
    # Your code here
}

Hint

Use a HashMap to count frequencies. Then push (frequency, number) pairs into a BinaryHeap. Pop the heap k times to get top elements.

4

Print the top K frequent elements

Print the vector top_k that contains the top k frequent elements.

DSA Rust

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

fn main() {
    let nums = vec![1, 1, 1, 2, 2, 3];
    let k = 2;

    let mut frequency_map = HashMap::new();
    for &num in &nums {
        *frequency_map.entry(num).or_insert(0) += 1;
    }

    let mut heap = BinaryHeap::new();
    for (&num, &freq) in &frequency_map {
        heap.push((freq, num));
    }

    let mut top_k = Vec::new();
    for _ in 0..k {
        if let Some((_, num)) = heap.pop() {
            top_k.push(num);
        }
    }

    // Print the top_k vector
    # Your code here
}

Hint

Use println!("{:?}", top_k); to print the vector.

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