Heap Extract Min or Max Bubble Down in DSA Rust

Mental Model

When we remove the top value from a heap, we replace it with the last value and then push that value down to restore the heap order.

Analogy: Imagine a pyramid of blocks where the top block is removed. You take the bottom block and place it on top, then slide it down to its correct spot so the pyramid stays stable.

Heap array: [10, 15, 20, 17, 25]
Index:      [0,  1,  2,  3,  4]

Min-heap property: parent ≤ children

Before extract:
      10
     /  \
   15    20
  /  \
17   25

After removing 10, replace with 25:
      25
     /  \
   15    20
  /  \
17   null

Then bubble down 25 to restore heap.

Dry Run Walkthrough

Input: Heap array: [10, 15, 20, 17, 25], extract min

Goal: Remove the smallest element (10) and restore the min-heap property by bubbling down the replaced element.

Step 1: Remove root (10) and replace it with last element (25)

[25, 15, 20, 17]
Heap tree:
      25
     /  \
   15    20
  /  \
17

Why: We remove the top element and fill the gap with the last element to keep the heap complete.

Step 2: Compare 25 with its children 15 and 20; swap with smallest child 15

[15, 25, 20, 17]
Heap tree:
      15
     /  \
   25    20
  /  \
17

Why: To restore min-heap, the parent must be smaller than children, so we swap with smaller child.

Step 3: Compare 25 with its children 17; swap with 17

[15, 17, 20, 25]
Heap tree:
      15
     /  \
   17    20
  /  \
25

Why: Continue bubbling down until the parent is smaller than children or no children left.

Step 4: 25 has no children, stop bubbling down

[15, 17, 20, 25]
Heap tree:
      15
     /  \
   17    20
  /  \
25

Why: Heap property restored; no further swaps needed.

Result:

[15, 17, 20, 25]
Extracted min: 10

Annotated Code

DSA Rust

struct MinHeap {
    data: Vec<Option<i32>>,
}

impl MinHeap {
    fn new(data: Vec<i32>) -> Self {
        let mut heap = MinHeap { data: data.into_iter().map(Some).collect() };
        heap.build_heap();
        heap
    }

    fn build_heap(&mut self) {
        let n = self.data.len();
        for i in (0..n / 2).rev() {
            self.bubble_down(i);
        }
    }

    fn bubble_down(&mut self, mut idx: usize) {
        let n = self.data.len();
        loop {
            let left = 2 * idx + 1;
            let right = 2 * idx + 2;
            let mut smallest = idx;

            if left < n {
                if let (Some(left_val), Some(smallest_val)) = (self.data[left], self.data[smallest]) {
                    if left_val < smallest_val {
                        smallest = left;
                    }
                }
            }

            if right < n {
                if let (Some(right_val), Some(smallest_val)) = (self.data[right], self.data[smallest]) {
                    if right_val < smallest_val {
                        smallest = right;
                    }
                }
            }

            if smallest != idx {
                self.data.swap(idx, smallest); // swap with smaller child
                idx = smallest; // continue bubbling down
            } else {
                break; // heap property restored
            }
        }
    }

    fn extract_min(&mut self) -> Option<i32> {
        let n = self.data.len();
        if n == 0 {
            return None; // empty heap
        }
        let min_val = self.data[0]?; // root value
        self.data[0] = self.data[n - 1]; // replace root with last element
        self.data.pop(); // remove last element
        if !self.data.is_empty() {
            self.bubble_down(0); // restore heap
        }
        Some(min_val)
    }

    fn print_heap(&self) {
        let vals: Vec<String> = self.data.iter().map(|v| match v {
            Some(x) => x.to_string(),
            None => "null".to_string(),
        }).collect();
        println!("{}", vals.join(" -> ") + " -> null");
    }
}

fn main() {
    let mut heap = MinHeap::new(vec![10, 15, 20, 17, 25]);
    println!("Initial heap:");
    heap.print_heap();

    let min = heap.extract_min();
    println!("Extracted min: {}", min.unwrap());

    println!("Heap after extract_min and bubble down:");
    heap.print_heap();
}

self.data[0] = self.data[n - 1]; // replace root with last element

replace root with last element to fill gap

self.data.pop(); // remove last element

remove last element since it moved to root

if !self.data.is_empty() { self.bubble_down(0); }

bubble down from root to restore heap property

if smallest != idx { self.data.swap(idx, smallest); idx = smallest; } else { break; }

swap with smaller child and continue bubbling down until heap property restored

Output

Initial heap:

10 -> 15 -> 20 -> 17 -> 25 -> null

Extracted min: 10

Heap after extract_min and bubble down:

15 -> 17 -> 20 -> 25 -> null

Complexity Analysis

Time: O(log n) because bubbling down moves down the height of the heap which is log n

Space: O(n) for storing the heap elements in an array

vs Alternative: Compared to rebuilding the heap from scratch (O(n)), bubbling down after extract is more efficient (O(log n))

Edge Cases

empty heap

extract_min returns None without error

DSA Rust

if n == 0 { return None; }

heap with one element

extract_min removes the only element and heap becomes empty

DSA Rust

self.data.pop();

heap where replaced element is already smaller than children

bubble_down stops immediately without swaps

DSA Rust

if smallest != idx { ... } else { break; }

When to Use This Pattern

When you need to remove the top element from a heap and maintain heap order, use extract with bubble down to efficiently restore the heap.

Common Mistakes

Mistake: Not swapping with the smallest child in a min-heap during bubble down
Fix: Always compare both children and swap with the smallest to maintain heap property

Mistake: Forgetting to remove the last element after moving it to root
Fix: Call pop() to remove the last element after replacing root

Summary

Removes the top element from a heap and restores heap order by pushing down the replaced element.

Use when you want to extract the min or max element from a heap efficiently.

The key is to replace the root with the last element and bubble it down to its correct position.

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