Kth Smallest Element Using Min Heap in DSA Rust

Mental Model

A min heap always keeps the smallest element at the top, so by removing the smallest element k times, we get the kth smallest.

Analogy: Imagine a pile of numbered cards where you always pick the smallest card on top. Picking the smallest card k times means the last card you pick is the kth smallest.

Min Heap Array Representation:
[2, 4, 5, 7, 8, 9]
Heap structure:
      2
     / \
    4   5
   / \   \
  7   8   9

Dry Run Walkthrough

Input: array: [7, 10, 4, 3, 20, 15], k=3

Goal: Find the 3rd smallest element in the array using a min heap

Step 1: Build min heap from array

[3, 7, 4, 10, 20, 15]

Why: Heapify the array so the smallest element is at the root

Step 2: Extract min (1st smallest): remove 3

[4, 7, 15, 10, 20]

Why: Remove smallest element to move towards kth smallest

Step 3: Extract min (2nd smallest): remove 4

[7, 10, 15, 20]

Why: Remove next smallest element

Step 4: Extract min (3rd smallest): remove 7

[10, 20, 15]

Why: The element removed now is the kth smallest

Result:

Heap after 3 extractions: [10, 20, 15]
3rd smallest element: 7

Annotated Code

DSA Rust

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

fn kth_smallest_element(arr: &[i32], k: usize) -> Option<i32> {
    // Create a min heap by wrapping elements with Reverse
    let mut min_heap = BinaryHeap::with_capacity(arr.len());
    for &num in arr {
        min_heap.push(Reverse(num)); // insert elements
    }

    let mut kth_min = None;
    for _ in 0..k {
        if let Some(Reverse(val)) = min_heap.pop() {
            kth_min = Some(val); // update kth_min each extraction
        } else {
            return None; // k is larger than array size
        }
    }
    kth_min
}

fn main() {
    let arr = [7, 10, 4, 3, 20, 15];
    let k = 3;
    match kth_smallest_element(&arr, k) {
        Some(val) => println!("{}th smallest element: {}", k, val),
        None => println!("k is out of range"),
    }
}

for &num in arr { min_heap.push(Reverse(num)); }

Insert all elements wrapped in Reverse to create a min heap

for _ in 0..k { if let Some(Reverse(val)) = min_heap.pop() { kth_min = Some(val); } else { return None; } }

Pop k times from min heap to get kth smallest element

Output

3th smallest element: 7

Complexity Analysis

Time: O(n + k log n) because building the heap takes O(n) and each of the k extractions takes O(log n)

Space: O(n) for storing the heap of all elements

vs Alternative: Sorting the array takes O(n log n), so using a min heap is more efficient when k is small compared to n

Edge Cases

k is zero or larger than array length

Function returns None indicating invalid input

DSA Rust

if let Some(Reverse(val)) = min_heap.pop() { ... } else { return None; }

array is empty

Function returns None because no elements exist

DSA Rust

if let Some(Reverse(val)) = min_heap.pop() { ... } else { return None; }

When to Use This Pattern

When you need the kth smallest element and want better than full sort, use a min heap to efficiently extract the smallest elements one by one.

Common Mistakes

Mistake: Using a max heap instead of a min heap for this problem
Fix: Use a min heap by wrapping elements with Reverse to keep smallest element on top

Mistake: Not handling the case when k is larger than the array size
Fix: Check if heap.pop() returns None and handle it by returning None or error

Summary

Finds the kth smallest element by building a min heap and extracting the smallest element k times.

Use when you want the kth smallest element without sorting the entire array.

The smallest element is always at the top of a min heap, so popping k times gives the kth smallest.

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