Heap Insert Operation Bubble Up in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the heap array after inserting 15 and bubbling up?

Given a max-heap represented as an array: [20, 18, 10, 12, 9], we insert the value 15 at the end and then bubble it up to restore the heap property. What is the resulting array?

DSA Rust

let mut heap = vec![20, 18, 10, 12, 9];
heap.push(15);
// Bubble up operation starts here
let mut idx = heap.len() - 1;
while idx > 0 {
    let parent = (idx - 1) / 2;
    if heap[idx] > heap[parent] {
        heap.swap(idx, parent);
        idx = parent;
    } else {
        break;
    }
}
println!("{:?}", heap);

A [20, 18, 15, 12, 9, 10]

B [20, 18, 10, 15, 9, 12]

C [20, 18, 15, 12, 9, 10, 15]

D [20, 18, 10, 12, 9, 15]

💡 Hint

Remember that bubble up swaps the inserted element with its parent while it is greater than the parent.

After inserting 15 at the end, the array is [20, 18, 10, 12, 9, 15]. Bubble up compares 15 with its parent 10 and swaps them. The array becomes [20, 18, 15, 12, 9, 10]. Since 15 is now less than its new parent 18, bubbling stops.

❓ Predict Output

intermediate

What is the heap array after inserting 25 and bubbling up?

Given a max-heap array: [30, 20, 15, 10, 8, 12], insert 25 and bubble it up. What is the resulting heap array?

DSA Rust

let mut heap = vec![30, 20, 15, 10, 8, 12];
heap.push(25);
let mut idx = heap.len() - 1;
while idx > 0 {
    let parent = (idx - 1) / 2;
    if heap[idx] > heap[parent] {
        heap.swap(idx, parent);
        idx = parent;
    } else {
        break;
    }
}
println!("{:?}", heap);

A [30, 20, 15, 10, 8, 12, 25]

B [30, 20, 25, 10, 8, 12, 15]

C [30, 25, 15, 10, 8, 12, 20]

D [30, 25, 20, 10, 8, 12, 15]

💡 Hint

Bubble up swaps the inserted value with parents while it is greater.

Insert 25 at the end: [30, 20, 15, 10, 8, 12, 25]. Compare 25 with parent 15, swap: [30, 20, 25, 10, 8, 12, 15]. Then compare 25 with new parent 20, swap: [30, 25, 20, 10, 8, 12, 15]. 25 is less than 30, so stop.

🔧 Debug

advanced

Identify the error in this bubble up implementation

This Rust code attempts to bubble up the last inserted element in a max-heap array. What error will it cause when run?

DSA Rust

let mut heap = vec![40, 30, 20, 15, 10];
heap.push(35);
let mut idx = heap.len() - 1;
while idx > 0 {
    let parent = idx / 2;
    if heap[idx] > heap[parent] {
        heap.swap(idx, parent);
        idx = parent;
    } else {
        break;
    }
}
println!("{:?}", heap);

A Runtime panic due to index out of bounds

B Correct output: [40, 35, 20, 15, 10, 30]

C Infinite loop because idx never decreases

D Compile-time error due to invalid syntax

💡 Hint

Check how parent index is calculated and if it can exceed array bounds.

The parent index is calculated as idx / 2, which is incorrect for zero-based arrays. For idx=1, parent=0 is correct, but for idx=2, parent=1 is correct. However, for idx=0, parent=0, but the loop stops at idx>0. The main problem is that for idx=1, parent=0, but for idx=5 (last element), parent=2 which is valid. However, the calculation is off by one compared to (idx - 1) / 2. This can cause incorrect parent indexing and potentially out of bounds access.

❓ Predict Output

advanced

What is the heap array after inserting 5 and bubbling up?

Given a max-heap array: [50, 30, 40, 10, 20], insert 5 and bubble it up. What is the resulting heap array?

DSA Rust

let mut heap = vec![50, 30, 40, 10, 20];
heap.push(5);
let mut idx = heap.len() - 1;
while idx > 0 {
    let parent = (idx - 1) / 2;
    if heap[idx] > heap[parent] {
        heap.swap(idx, parent);
        idx = parent;
    } else {
        break;
    }
}
println!("{:?}", heap);

A [50, 30, 40, 10, 20, 10]

B [50, 30, 40, 10, 20, 5]

C [50, 30, 40, 10, 20, 20]

D [50, 30, 40, 10, 20, 40]

💡 Hint

Since 5 is less than its parent, no swaps happen.

After inserting 5 at the end, the array is [50, 30, 40, 10, 20, 5]. Bubble up compares 5 with its parent 40. Since 5 is less, no swap occurs and bubbling stops immediately.

❓ Predict Output

expert

What is the heap array after multiple insertions and bubble ups?

Starting with an empty max-heap array, insert the values in this order: 10, 20, 5, 30, 25. After each insertion, bubble up to maintain the heap property. What is the final heap array?

DSA Rust

let mut heap = Vec::new();
for &val in &[10, 20, 5, 30, 25] {
    heap.push(val);
    let mut idx = heap.len() - 1;
    while idx > 0 {
        let parent = (idx - 1) / 2;
        if heap[idx] > heap[parent] {
            heap.swap(idx, parent);
            idx = parent;
        } else {
            break;
        }
    }
}
println!("{:?}", heap);

A [25, 30, 20, 10, 5]

B [30, 25, 5, 10, 20]

C [30, 25, 20, 10, 5]

D [30, 20, 25, 10, 5]

💡 Hint

Insert each value and bubble up step-by-step, tracking the array after each insertion.

Insert 10: [10]
Insert 20: [20, 10] (20 bubbles up)
Insert 5: [20, 10, 5]
Insert 30: [30, 20, 5, 10] (30 bubbles up to root)
Insert 25: [30, 25, 5, 10, 20] (25 bubbles up swapping with 10 and then 20)

Final heap array is [30, 25, 20, 10, 5].

Practice

1. What is the main purpose of the bubble up operation during a heap insert?

easy

A. To swap the root with the last element

B. To restore the heap property by moving the inserted element up

C. To sort all elements in ascending order

D. To remove the smallest element from the heap

Solution

1. Step 1: Understand heap property

   A heap must maintain a specific order, usually parent nodes are greater (max-heap) or smaller (min-heap) than their children.

2. Step 2: Role of bubble up

   When a new element is inserted at the end, bubble up moves it up to restore the heap property if violated.

3. Final Answer:

   To restore the heap property by moving the inserted element up -> Option B

4. Quick Check:

   Bubble up fixes heap order after insert [OK]

Hint: Bubble up fixes heap order by moving new element up [OK]

Common Mistakes:

• Confusing bubble up with removing elements
• Thinking bubble up sorts the entire heap
• Believing bubble up swaps root with last element

2. Which Rust code snippet correctly swaps a child and its parent during bubble up in a max-heap?

easy

A. heap.swap(child_index, parent_index);

B. heap.insert(child_index, parent_index);

C. heap.remove(child_index);

D. heap.push(parent_index);

Solution

1. Step 1: Identify swap method usage

   To exchange two elements in a vector, Rust's Vec has a swap method taking two indices.

2. Step 2: Confirm correct parameters

   Swapping child and parent indices restores heap order during bubble up.

3. Final Answer:

   heap.swap(child_index, parent_index); -> Option A

4. Quick Check:

   swap() exchanges elements by index [OK]

Hint: Use Vec.swap(child, parent) to exchange elements [OK]

Common Mistakes:

• Using insert instead of swap
• Calling remove which deletes elements
• Using push which adds elements

3. Given the max-heap represented by the array [50, 30, 40, 10, 20], what will be the heap array after inserting 45 and performing bubble up?

medium

A. [50, 45, 40, 10, 20, 30]

B. [50, 30, 40, 10, 20, 45]

C. [50, 30, 45, 10, 20, 40]

D. [45, 30, 50, 10, 20, 40]

Solution

1. Step 1: Insert 45 at the end

   Array becomes [50, 30, 40, 10, 20, 45].

2. Step 2: Bubble up 45

   Parent of index 5 is index 2 (value 40). Since 45 > 40, swap them. New array: [50, 30, 45, 10, 20, 40].

3. Step 3: Check next parent

   Parent of index 2 is index 0 (value 50). 45 < 50, stop bubbling up.

4. Final Answer:

   [50, 30, 45, 10, 20, 40] -> Option C

5. Quick Check:

   Insert then bubble up swaps with parent if bigger [OK]

Hint: Insert at end, swap up while bigger than parent [OK]

Common Mistakes:

• Not swapping 45 with 40
• Swapping 45 with 30 incorrectly
• Stopping bubble up too early

4. In the following Rust code for bubble up, what is the bug?

fn bubble_up(heap: &mut Vec<i32>, mut index: usize) {
    while index > 0 {
        let parent = (index - 1) / 2;
        if heap[index] > heap[parent] {
            heap.swap(index, parent);
            index = parent;
        }
    }
}

medium

A. Loop condition should be index >= 0

B. Incorrect parent calculation formula

C. Using swap instead of insert

D. Missing update of index when no swap occurs, causing infinite loop

Solution

1. Step 1: Analyze loop behavior

   Loop runs while index > 0. Inside, swap and update index if heap[index] > heap[parent].

2. Step 2: Identify missing else case

   If heap[index] <= heap[parent], index is not updated, so loop never ends causing infinite loop.

3. Final Answer:

   Missing update of index when no swap occurs, causing infinite loop -> Option D

4. Quick Check:

   Loop must update index or break to avoid infinite loop [OK]

Hint: Always update index or break in bubble up loop [OK]

Common Mistakes:

• Ignoring infinite loop possibility
• Wrong parent index formula
• Confusing swap with insert
• Using invalid loop condition

5. You have a min-heap represented by [5, 10, 15, 20, 25]. You insert 12. After bubble up, what is the correct heap array?

hard

A. [5, 10, 12, 20, 25, 15]

B. [5, 10, 15, 20, 25, 12]

C. [5, 12, 10, 20, 25, 15]

D. [5, 10, 15, 12, 25, 20]

Solution

1. Step 1: Insert 12 at the end

   Array becomes [5, 10, 15, 20, 25, 12].

2. Step 2: Bubble up 12 in min-heap

   Parent of index 5 is index 2 (value 15). Since 12 < 15, swap them. New array: [5, 10, 12, 20, 25, 15].

3. Step 3: Check next parent

   Parent of index 2 is index 0 (value 5). 12 > 5, stop bubbling up.

4. Final Answer:

   [5, 10, 12, 20, 25, 15] -> Option A

5. Quick Check:

   Min-heap bubble up swaps if child smaller than parent [OK]

Hint: In min-heap, bubble up swaps smaller child with parent [OK]

Common Mistakes:

• Not swapping 12 with 15
• Stopping bubble up too early
• Confusing min-heap with max-heap rules