Kth Smallest Element Using Min Heap in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a min heap from the given vector.

DSA Rust

let mut heap = std::collections::BinaryHeap::[1](vec);

Drag options to blanks, or click blank then click option'

Anew

Bdefault

Cfrom

Dwith_capacity

Attempts:

3 left

💡 Hint

Common Mistakes

Using new() creates an empty heap, not from a vector.

with_capacity() only reserves space, does not build from vector.

The from function creates a heap from an existing vector.

2fill in blank

medium

Complete the code to pop the smallest element from the min heap.

DSA Rust

let smallest = heap.[1]().unwrap();

Drag options to blanks, or click blank then click option'

Apop

Bpeek

Cremove

Dextract

Attempts:

3 left

💡 Hint

Common Mistakes

Using peek() only returns a reference, does not remove.

remove() and extract() are not methods of BinaryHeap.

The pop method removes and returns the smallest element in a min heap.

3fill in blank

hard

Fix the error in the code to create a min heap by reversing the order.

DSA Rust

let mut heap = std::collections::BinaryHeap::from(vec.into_iter().map(|x| std::cmp::Reverse([1])).collect());

Drag options to blanks, or click blank then click option'

Ax

Bx + 1

C-x

Dx * 2

Attempts:

3 left

💡 Hint

Common Mistakes

Changing the value inside Reverse breaks the heap order.

Using expressions like x + 1 or -x is incorrect here.

We wrap each element x with Reverse(x) to make a min heap.

4fill in blank

hard

Fill both blanks to complete the loop that pops k-1 smallest elements.

DSA Rust

for _ in 0..[1] {
    heap.[2]();
}

Drag options to blanks, or click blank then click option'

Ak - 1

Bk + 1

Cpop

Dpeek

Attempts:

3 left

💡 Hint

Common Mistakes

Using peek() does not remove elements.

Looping k+1 times removes too many elements.

We pop k - 1 times to remove the smallest elements before the kth.

Use pop() to remove elements.

5fill in blank

hard

Fill all three blanks to return the kth smallest element from the min heap.

DSA Rust

let kth_smallest = heap.[1]().map(|std::cmp::Reverse([2])| [3]).unwrap();

Drag options to blanks, or click blank then click option'

Apop

Bval

Dpeek

Attempts:

3 left

💡 Hint

Common Mistakes

Using peek() returns a reference, not the value.

Not unwrapping Reverse causes type errors.

Pop the top element, unwrap the Reverse wrapper, and get the value.

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