Heap Insert Operation Bubble Up in DSA Rust

Mental Model

When adding a new number to a heap, we place it at the end and then move it up until the heap rules are correct again.

Analogy: Imagine adding a new player to a team lineup at the end, then letting them move up the ranks by swapping places with players who are less skilled until everyone is in the right order.

Heap as array:
[10, 15, 20, 17, 25]
Index:  0   1   2   3   4
New value 13 added at end:
[10, 15, 20, 17, 25, 13]
                      ↑

Dry Run Walkthrough

Input: heap: [10, 15, 20, 17, 25], insert value 13

Goal: Insert 13 and restore heap property by moving it up if needed

Step 1: Add 13 at the end of the heap array

[10, 15, 20, 17, 25, 13 ↑]

Why: New value must start at the last position before bubbling up

Step 2: Compare 13 with its parent 20; since 13 < 20, swap them

[10, 15, 13 ↑, 17, 25, 20]

Why: Heap rule violated, smaller child must move up

Step 3: Compare 13 with new parent 15; since 13 < 15, swap them

[10, 13 ↑, 15, 17, 25, 20]

Why: Heap rule violated, smaller child must move up

Step 4: Compare 13 with new parent 10; since 13 > 10, stop bubbling up

[10, 13, 15, 17, 25, 20]

Why: Heap property restored, no more swaps needed

Result:

[10, 13, 15, 17, 25, 20] final heap array

Annotated Code

DSA Rust

struct MinHeap {
    data: Vec<i32>,
}

impl MinHeap {
    fn new() -> Self {
        MinHeap { data: Vec::new() }
    }

    fn insert(&mut self, val: i32) {
        self.data.push(val); // add at end
        let mut idx = self.data.len() - 1;

        while idx > 0 {
            let parent = (idx - 1) / 2;
            if self.data[idx] < self.data[parent] {
                self.data.swap(idx, parent); // swap child and parent
                idx = parent; // move up to parent's index
            } else {
                break; // heap property restored
            }
        }
    }

    fn print_heap(&self) {
        for val in &self.data {
            print!("{} ", val);
        }
        println!();
    }
}

fn main() {
    let mut heap = MinHeap::new();
    heap.data = vec![10, 15, 20, 17, 25];
    heap.insert(13);
    heap.print_heap();
}

self.data.push(val); // add at end

Add new value at the last position in the heap array

let mut idx = self.data.len() - 1;

Start bubbling up from the last index

while idx > 0 {

Continue bubbling up until root or heap property restored

let parent = (idx - 1) / 2;

Calculate parent index of current node

if self.data[idx] < self.data[parent] {

Check if child is smaller than parent to decide swap

self.data.swap(idx, parent); // swap child and parent

Swap child with parent to move smaller value up

idx = parent; // move up to parent's index

Update current index to parent's index for next iteration

else { break; }

Stop bubbling up when heap property is satisfied

Output

10 13 15 17 25 20 

Complexity Analysis

Time: O(log n) because in worst case the new element moves up the height of the heap

Space: O(1) because insertion is done in place without extra space

vs Alternative: Compared to rebuilding the heap from scratch (O(n)), bubbling up is faster for single insertions

Edge Cases

Insert into empty heap

Value is simply added as root with no bubbling

DSA Rust

while idx > 0 {

Insert value larger than all existing values

Value stays at the end, no swaps occur

DSA Rust

if self.data[idx] < self.data[parent] {

Insert value smaller than root

Value bubbles all the way up to root

DSA Rust

idx = parent;

When to Use This Pattern

When you need to add an element to a heap and keep it ordered, use bubble up to restore heap property efficiently.

Common Mistakes

Mistake: Not updating the current index after swapping with parent
Fix: Assign idx = parent after swap to continue bubbling up

Mistake: Comparing child with wrong parent index
Fix: Calculate parent as (idx - 1) / 2 correctly

Summary

It adds a new value to the heap and moves it up until the heap order is correct.

Use it when inserting a new element into a heap to keep the heap property.

The key insight is that the new element only needs to move up, swapping with parents, until it fits.

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