Heap Extract Min or Max Bubble Down in DSA Rust - Execution Trace

Concept Flow - Heap Extract Min or Max Bubble Down

Start: Root Node to Extract

↓

Replace Root with Last Element

↓

Remove Last Element

↓

Bubble Down: Compare with Children

↓

Left Child < Right Child?

↓

Swap with Smaller Child

↓

Repeat Bubble Down Until Heap Property Restored

↓

Done

This flow shows how extracting the root from a heap replaces it with the last element, then bubbles that element down by swapping with smaller children until the heap property is restored.

Execution Sample

DSA Rust

fn extract_min(heap: &mut Vec<i32>) -> Option<i32> {
    if heap.is_empty() { return None; }
    let min = heap[0];
    let last = heap.pop().unwrap();
    if !heap.is_empty() {
        heap[0] = last;
        bubble_down(heap, 0);
    }
    Some(min)
}

Extracts the minimum element from a min-heap and restores heap property by bubbling down.

Execution Table

Step	Operation	Heap Array State	Pointer Changes	Visual State
1	Initial heap	[10, 15, 30, 40, 50, 100, 40]	head = 0	Array: [10, 15, 30, 40, 50, 100, 40] Tree: 10 / \ 15 30 / \ / \ 40 50 100 40
2	Extract root (10), replace with last element (40)	[40, 15, 30, 40, 50, 100]	head = 0 (replaced), last element removed	Array: [40, 15, 30, 40, 50, 100] Tree: 40 / \ 15 30 / \ / 40 50 100
3	Bubble down step 1: compare 40 with children 15 and 30	[40, 15, 30, 40, 50, 100]	current = 0, left = 1, right = 2	40 > 15 and 30, swap with smaller child 15
4	After swap with 15	[15, 40, 30, 40, 50, 100]	current = 1 (moved down)	Array: [15, 40, 30, 40, 50, 100] Tree: 15 / \ 40 30 / \ / 40 50 100
5	Bubble down step 2: compare 40 (index 1) with children 40 and 50	[15, 40, 30, 40, 50, 100]	current = 1, left = 3, right = 4	40 <= 40 and 50, no swap needed
6	Bubble down complete, heap property restored	[15, 40, 30, 40, 50, 100]	No pointer changes	Final heap: 15 / \ 40 30 / \ / 40 50 100

💡 Bubble down stops when current node is smaller than both children or no children exist.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 5	Final
heap	[10, 15, 30, 40, 50, 100, 40]	[40, 15, 30, 40, 50, 100]	[15, 40, 30, 40, 50, 100]	[15, 40, 30, 40, 50, 100]	[15, 40, 30, 40, 50, 100]
current	0	0	1	1	1
left	1	1	3	3	3
right	2	2	4	4	4

Key Moments - 3 Insights

Why do we replace the root with the last element before bubbling down?

Replacing the root with the last element keeps the heap complete (no gaps). Then bubbling down restores the heap order. See execution_table step 2 where root 10 is replaced by last element 40.

Why do we swap with the smaller child during bubble down?

To maintain the min-heap property, the parent must be smaller than both children. Swapping with the smaller child ensures the smallest element moves up. See step 3 and 4 where 40 swaps with 15, the smaller child.

When does the bubble down process stop?

It stops when the current node is smaller than both children or has no children. In step 5, 40 is smaller or equal to its children, so no swap happens and bubble down ends.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the heap array state?

A [15, 40, 30, 40, 50, 100]

B [40, 15, 30, 40, 50, 100]

C [10, 15, 30, 40, 50, 100, 40]

D [15, 30, 40, 40, 50, 100]

💡 Hint

Check the 'Heap Array State' column in execution_table row for step 4.

At which step does the bubble down process stop?

A Step 3

B Step 5

C Step 2

D Step 6

💡 Hint

Look for the step where no swap occurs and bubble down ends in execution_table.

If the last element was smaller than both children, what would happen during bubble down?

A Swap with the smaller child repeatedly

B Swap with the larger child

C No swaps, bubble down stops immediately

D Heap becomes invalid

💡 Hint

Refer to the bubble down stopping condition in execution_table step 5.

Concept Snapshot

Heap Extract Min or Max Bubble Down:
- Remove root (min or max) from heap
- Replace root with last element
- Remove last element
- Bubble down: swap with smaller (min-heap) or larger (max-heap) child
- Repeat until heap property restored
- Ensures complete tree and heap order

Full Transcript

Heap extract min or max removes the root element from the heap. To keep the heap complete, the last element replaces the root. Then, bubble down compares this element with its children and swaps with the smaller child in a min-heap (or larger in max-heap) to restore heap order. This repeats until the element is smaller than both children or no children remain. The process ensures the heap remains a complete binary tree and maintains the heap property after extraction.

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