Heap Extract Min or Max Bubble Down in DSA Rust - Build from Scratch

Heap Extract Min or Max Bubble Down

📖 Scenario: Imagine you are managing a priority queue for tasks using a heap data structure. When you remove the highest priority task (minimum or maximum), you need to reorganize the heap to keep it valid. This reorganization is called "bubble down".In this project, you will implement the bubble down step after extracting the root from a heap represented as a vector.

🎯 Goal: You will build a Rust program that extracts the root element from a heap (min-heap or max-heap) and then performs the bubble down operation to restore the heap property.This will help you understand how heaps maintain order after removal.

📋 What You'll Learn

Create a vector called heap with exact values representing a heap

Create a variable heap_size to track the current size of the heap

Implement a bubble_down function that restores the heap property after extraction

Extract the root element and update the heap accordingly

Print the heap vector after bubble down to show the updated heap

💡 Why This Matters

🌍 Real World

Heaps are used in priority queues, scheduling tasks, and algorithms like Dijkstra's shortest path. Extracting the min or max element efficiently is key in these applications.

💼 Career

Understanding heap operations is important for software engineers working on performance-critical systems, real-time processing, and algorithm optimization.

1

Create the initial heap vector

Create a vector called heap with these exact values: vec![10, 15, 20, 17, 25]. This represents a min-heap.

DSA Rust

# Create the heap vector with given values
# Your code here

Hint

Use let mut heap = vec![10, 15, 20, 17, 25]; to create the heap vector.

2

Add a variable to track heap size

Create a variable called heap_size and set it to the length of heap using heap.len().

DSA Rust

fn main() {
    let mut heap = vec![10, 15, 20, 17, 25];
    // Create heap_size variable
    # Your code here
}

Hint

Use let mut heap_size = heap.len(); to track the current heap size.

3

Implement the bubble_down function

Write a function called bubble_down that takes heap: &mut Vec<i32>, start: usize, and heap_size: usize. It should restore the min-heap property by swapping the element at start down the tree until the heap property is valid. Use a loop and compare with left and right children at indices 2 * index + 1 and 2 * index + 2.

DSA Rust

fn main() {
    let mut heap = vec![10, 15, 20, 17, 25];
    let mut heap_size = heap.len();

    // Implement bubble_down function below
    # Your code here
}

Hint

Use a loop to compare the current element with its children and swap if needed. Stop when no swaps are needed.

4

Extract root and bubble down, then print heap

In main, remove the root element by swapping heap[0] with heap[heap_size - 1], then decrease heap_size by 1. Call bubble_down(&mut heap, 0, heap_size) to restore the heap. Finally, print the heap vector.

DSA Rust

fn bubble_down(heap: &mut Vec, start: usize, heap_size: usize) {
    let mut index = start;
    loop {
        let left = 2 * index + 1;
        let right = 2 * index + 2;
        let mut smallest = index;

        if left < heap_size && heap[left] < heap[smallest] {
            smallest = left;
        }
        if right < heap_size && heap[right] < heap[smallest] {
            smallest = right;
        }

        if smallest == index {
            break;
        }

        heap.swap(index, smallest);
        index = smallest;
    }
}

fn main() {
    let mut heap = vec![10, 15, 20, 17, 25];
    let mut heap_size = heap.len();

    // Extract root and bubble down
    # Your code here
}

Hint

Swap the root with the last element, reduce heap size, call bubble_down from index 0, then print the heap slice up to heap_size.

Practice

1. What is the main purpose of the bubble down operation in a min-heap after extracting the minimum element?

easy

A. To insert a new element at the bottom of the heap

B. To remove all elements smaller than the root

C. To swap the last element with the root without any further changes

D. To restore the heap property by moving the root element down to its correct position

Solution

1. Step 1: Understand extract-min operation

   Extracting the minimum removes the root, so the last element moves to the root.

2. Step 2: Purpose of bubble down

   Bubble down moves this new root down to restore the min-heap property by swapping with smaller children.

3. Final Answer:

   To restore the heap property by moving the root element down to its correct position -> Option D

4. Quick Check:

   Bubble down fixes heap after extract-min [OK]

Hint: Bubble down fixes heap from root after extract-min [OK]

Common Mistakes:

• Thinking bubble down inserts new elements
• Assuming bubble down removes elements
• Confusing bubble down with bubble up

2. Which of the following Rust function signatures correctly represents a bubble down operation for a min-heap stored in a vector?

easy

A. fn bubble_down(&heap: Vec<i32>, index: usize)

B. fn bubble_down(heap: &mut Vec<i32>, index: usize)

C. fn bubble_down(heap: Vec<i32>, index: usize) -> Vec<i32>

D. fn bubble_down(heap: &Vec<i32>, index: usize)

Solution

1. Step 1: Identify mutability needs

   Bubble down modifies the heap, so it needs a mutable reference to the vector.

2. Step 2: Check parameter types

   fn bubble_down(heap: &mut Vec<i32>, index: usize) uses &mut Vec<i32>, allowing in-place changes without ownership transfer.

3. Final Answer:

   fn bubble_down(heap: &mut Vec<i32>, index: usize) -> Option B

4. Quick Check:

   Mutable reference needed for in-place heap changes [OK]

Hint: Use &mut Vec for in-place heap modification [OK]

Common Mistakes:

• Passing Vec by value causing ownership move
• Using immutable references when mutation is needed
• Incorrect parameter syntax

3. Consider the following Rust code snippet for a min-heap stored in a vector:

let mut heap = vec![1, 3, 6, 5, 9, 8];
heap[0] = heap.pop().unwrap();
bubble_down(&mut heap, 0);
println!("{:?}", heap);

If bubble_down correctly restores the min-heap property, what will be the printed vector?

medium

A. [3, 5, 8, 6, 9]

B. [6, 3, 8, 5, 9]

C. [3, 5, 6, 8, 9]

D. [5, 3, 6, 8, 9]

Solution

1. Step 1: Understand initial heap and pop

   Initial heap: [1,3,6,5,9,8]. After pop(), last element 8 is removed and placed at root: heap[0] = 8, heap = [8,3,6,5,9]

2. Step 2: Bubble down from root

   Compare 8 with children 3 and 6; smallest is 3, swap 8 and 3: [3,8,6,5,9]. Next, bubble down 8 at index 1 with children 5 and 9; smallest is 5, swap: [3,5,6,8,9]. No further swaps needed.

3. Final Answer:

   [3, 5, 6, 8, 9] -> Option C

4. Quick Check:

   Bubble down swaps to restore min-heap [OK]

Hint: Replace root with last, then bubble down to fix heap [OK]

Common Mistakes:

• Not swapping with smallest child
• Stopping bubble down too early
• Incorrect pop and root replacement

4. Given this Rust bubble down function snippet for a max-heap, identify the bug:

fn bubble_down(heap: &mut Vec<i32>, mut index: usize) {
    let len = heap.len();
    loop {
        let left = 2 * index + 1;
        let right = 2 * index + 2;
        let mut largest = index;
        if left < len && heap[left] > heap[largest] {
            largest = left;
        }
        if right < len && heap[right] > heap[largest] {
            largest = right;
        }
        if largest == index {
            break;
        }
        heap.swap(index, largest);
        // Missing update of index here
    }
}

medium

A. The index variable is not updated after swapping, causing an infinite loop

B. The function uses a min-heap condition instead of max-heap

C. The left and right child indices are calculated incorrectly

D. The swap function is used incorrectly

Solution

1. Step 1: Analyze loop behavior

   After swapping, the index must move to the child's position to continue bubbling down.

2. Step 2: Identify missing update

   The code does not update index = largest after swap, so loop repeats with same index causing infinite loop.

3. Final Answer:

   The index variable is not updated after swapping, causing an infinite loop -> Option A

4. Quick Check:

   Update index after swap to continue bubble down [OK]

Hint: Always update index after swap in bubble down loop [OK]

Common Mistakes:

• Forgetting to update index after swap
• Mixing min-heap and max-heap conditions
• Incorrect child index calculations

5. You have a max-heap represented as [50, 30, 40, 10, 20, 35]. After extracting the maximum element (50), you replace the root with the last element and perform bubble down. What is the final heap array after bubble down completes?

hard

A. [40, 30, 35, 10, 20]

B. [40, 30, 10, 20, 35]

C. [35, 30, 40, 10, 20]

D. [35, 30, 20, 10, 40]

Solution

1. Step 1: Replace root with last element

   Remove 50, move last element 35 to root: [35, 30, 40, 10, 20]

2. Step 2: Bubble down from root

   Compare 35 with children 30 and 40; largest is 40, swap: [40, 30, 35, 10, 20]. Next, bubble down 35 at index 2 with children none (leaf), stop.

3. Final Answer:

   [40, 30, 35, 10, 20] -> Option A

4. Quick Check:

   Bubble down swaps root with largest child until heap restored [OK]

Hint: Replace root with last, bubble down swapping with largest child [OK]

Common Mistakes:

• Not swapping with largest child
• Stopping bubble down too early
• Incorrect root replacement