Kth Smallest Element Using Min Heap in DSA Rust - Build from Scratch

Kth Smallest Element Using Min Heap

📖 Scenario: Imagine you have a list of exam scores from students. You want to find the kth smallest score to understand the lower range of performance.

🎯 Goal: You will build a Rust program that uses a min heap to find the kth smallest element in a list of numbers.

📋 What You'll Learn

Create a vector called numbers with the exact values: 12, 3, 5, 7, 19

Create a variable called k and set it to 3

Use a BinaryHeap as a min heap to find the kth smallest element

Print the kth smallest element exactly as shown

💡 Why This Matters

🌍 Real World

Finding the kth smallest element is useful in statistics, data analysis, and real-time systems where you want to quickly find thresholds or percentiles.

💼 Career

Understanding heaps and selection algorithms is important for software engineers working on performance-critical applications, databases, and systems programming.

1

Create the list of numbers

Create a vector called numbers with the exact values 12, 3, 5, 7, 19.

DSA Rust

# Create a vector called numbers with the values 12, 3, 5, 7, 19
# Your code here

Hint

Use vec![...] to create the vector with the exact numbers.

2

Set the value of k

Create a variable called k and set it to 3.

DSA Rust

let numbers = vec![12, 3, 5, 7, 19];
# Create a variable k and set it to 3
# Your code here

Hint

Use let k = 3; to create the variable.

3

Use a min heap to find the kth smallest element

Use std::collections::BinaryHeap as a min heap by pushing the negative of each number from numbers. Then pop k-1 elements and get the kth smallest element by popping once more and negating it back.

DSA Rust

let numbers = vec![12, 3, 5, 7, 19];
let k = 3;
// Use a BinaryHeap as a min heap by pushing negative values
// Pop k-1 elements
// Pop kth element and negate it back
# Your code here

Hint

Remember to push negative numbers to simulate a min heap using BinaryHeap which is a max heap by default.

4

Print the kth smallest element

Print the variable kth_smallest using println! exactly as println!("{}", kth_smallest);.

DSA Rust

use std::collections::BinaryHeap;

let numbers = vec![12, 3, 5, 7, 19];
let k = 3;

let mut min_heap = BinaryHeap::new();
for &num in &numbers {
    min_heap.push(-num);
}

for _ in 0..(k - 1) {
    min_heap.pop();
}

let kth_smallest = -min_heap.pop().unwrap();

// Print the kth smallest element
# Your code here

Hint

Use println!("{}", kth_smallest); to print the result.

Practice

1. What is the main idea behind finding the kth smallest element using a min heap?

easy

A. Use a hash map to count frequencies and find the kth smallest

B. Sort the array and pick the element at index k

C. Build a max heap and extract the maximum element k times

D. Build a min heap from the array and extract the minimum element k times

Solution

1. Step 1: Understand min heap property

   A min heap always keeps the smallest element at the root, so extracting the root gives the smallest element.

2. Step 2: Extract minimum k times

   By removing the root k times, the last extracted element is the kth smallest.

3. Final Answer:

   Build a min heap and extract minimum k times -> Option D

4. Quick Check:

   Min heap extraction = kth smallest element [OK]

Hint: Extract min from min heap k times to get kth smallest [OK]

Common Mistakes:

• Using max heap instead of min heap
• Sorting array instead of using heap
• Confusing kth smallest with kth largest

2. Which Rust code snippet correctly creates a min heap from a vector nums?

easy

A. let mut heap = std::collections::BinaryHeap::from(nums.iter().map(|&x| Reverse(x)).collect::());

B. let mut heap = std::collections::BinaryHeap::from(nums);

C. let mut heap = std::collections::BinaryHeap::new(); for &num in &nums { heap.push(num); }

D. let mut heap = nums.sort();

Solution

1. Step 1: Understand Rust's BinaryHeap default behavior

   Rust's BinaryHeap is a max heap by default, so to create a min heap, we wrap elements with Reverse.

2. Step 2: Use Reverse wrapper to invert order

   Mapping each element to Reverse(x) and collecting into a vector allows building a min heap.

3. Final Answer:

   Use BinaryHeap with Reverse wrapper on elements -> Option A

4. Quick Check:

   BinaryHeap + Reverse = min heap in Rust [OK]

Hint: Wrap elements with Reverse to make min heap in Rust [OK]

Common Mistakes:

• Using BinaryHeap directly creates max heap
• Sorting vector does not create a heap
• Forgetting to collect after map

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

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn main() {
    let nums = vec![7, 10, 4, 3, 20, 15];
    let k = 3;
    let mut heap = BinaryHeap::from(nums.iter().map(|&x| Reverse(x)).collect::());
    let mut kth_smallest = 0;
    for _ in 0..k {
        if let Some(Reverse(val)) = heap.pop() {
            kth_smallest = val;
        }
    }
    println!("{}", kth_smallest);
}

medium

A. 7

B. 10

C. 4

D. 3

Solution

1. Step 1: Build min heap from nums

   The min heap contains elements: 3, 4, 7, 10, 15, 20 with 3 at root.

2. Step 2: Extract min 3 times

   Extracted elements in order: 3 (1st), 4 (2nd), 7 (3rd). The 3rd extracted is 7.

3. Final Answer:

   7 -> Option A

4. Quick Check:

   3rd smallest in [7,10,4,3,20,15] = 7 [OK]

Hint: Extract min k times from min heap to get kth smallest [OK]

Common Mistakes:

• Confusing kth smallest with kth largest
• Not using Reverse wrapper for min heap
• Off-by-one error in loop

4. Identify the error in this Rust code snippet that tries to find the 2nd smallest element using a min heap:

use std::collections::BinaryHeap;

fn main() {
    let nums = vec![5, 3, 8, 1];
    let k = 2;
    let mut heap = BinaryHeap::from(nums);
    let mut kth_smallest = 0;
    for _ in 0..k {
        if let Some(val) = heap.pop() {
            kth_smallest = val;
        }
    }
    println!("{}", kth_smallest);
}

medium

A. The loop should run from 1 to k inclusive

B. BinaryHeap creates a max heap, so it finds kth largest, not smallest

C. The vector nums is empty, causing runtime error

D. The variable kth_smallest is not initialized

Solution

1. Step 1: Check heap type created by BinaryHeap::from

   BinaryHeap in Rust is a max heap by default, so it pops largest elements first.

2. Step 2: Understand effect on kth smallest search

   Extracting from max heap gives kth largest, not kth smallest, so result is incorrect.

3. Final Answer:

   BinaryHeap creates max heap, finds kth largest not smallest -> Option B

4. Quick Check:

   BinaryHeap default = max heap [OK]

Hint: Rust BinaryHeap is max heap by default, use Reverse for min heap [OK]

Common Mistakes:

• Assuming BinaryHeap is min heap
• Incorrect loop range
• Ignoring Reverse wrapper

5. Given a large vector nums with 1 million elements, which approach is most efficient to find the 10th smallest element using a min heap in Rust?

hard

A. Build a min heap of all elements and pop 10 times

B. Use a hash map to count frequencies and find 10th smallest

C. Build a max heap of size 10 and iterate over nums pushing elements

D. Sort the entire vector and pick element at index 9

Solution

1. Step 1: Analyze building min heap of all elements

   Building min heap of 1 million elements uses O(n) time but popping 10 times is O(k log n), still costly in memory and time.

2. Step 2: Use max heap of size k to track smallest elements

   Maintaining a max heap of size 10 while iterating allows efficient O(n log k) time and less memory.

3. Step 3: Sorting entire vector is O(n log n), slower than heap approach

   Sorting 1 million elements is expensive compared to heap of size 10.

4. Final Answer:

   Build max heap of size 10 and iterate over nums pushing elements -> Option C

5. Quick Check:

   Max heap size k = efficient kth smallest [OK]

Hint: Use max heap of size k for large data to find kth smallest [OK]

Common Mistakes:

• Building min heap of all elements wastes memory
• Sorting entire vector is slower
• Using hash map is unnecessary overhead