Heap Insert Operation Bubble Up in DSA Rust - Build from Scratch

Heap Insert Operation Bubble Up

📖 Scenario: Imagine you are managing a priority queue for tasks where the highest priority task should always come first. You will build a simple max-heap to keep tasks ordered by priority.

🎯 Goal: You will create a max-heap represented as a vector, add a new element to it, and then perform the bubble up operation to maintain the max-heap property.

📋 What You'll Learn

Create a vector called heap with initial values representing a max-heap

Create a variable called new_value with the value to insert

Implement the bubble up logic to restore the max-heap property after insertion

Print the heap vector after insertion and bubble up

💡 Why This Matters

🌍 Real World

Priority queues are used in task scheduling, network packet management, and event simulation where the highest priority item must be processed first.

💼 Career

Understanding heap insertions and bubble up operations is essential for roles involving algorithms, system design, and performance optimization.

1

Create the initial max-heap vector

Create a vector called heap with these exact values: vec![100, 50, 30, 20, 40]

DSA Rust

# Create the initial max-heap vector called heap
# Your code here

Hint

Use let mut heap = vec![100, 50, 30, 20, 40]; to create a mutable vector.

2

Add the new value to insert

Create a variable called new_value and set it to 60. Then append new_value to the heap vector.

DSA Rust

let mut heap = vec![100, 50, 30, 20, 40];
# Create new_value = 60 and append it to heap
# Your code here

Hint

Use let new_value = 60; and heap.push(new_value); to add the new value.

3

Implement the bubble up operation

Write a while loop to bubble up the last element in heap. Use index to track the current position starting from the last index. Swap the element with its parent if it is greater, and update index to the parent's index. Stop when the element is at the root or no longer greater than its parent.

DSA Rust

let mut heap = vec![100, 50, 30, 20, 40];
let new_value = 60;
heap.push(new_value);

// Bubble up the last element
# Your code here

Hint

Use a while loop with index and calculate parent_index as (index - 1) / 2. Swap if child is greater than parent.

4

Print the heap after insertion and bubble up

Print the heap vector using println!("{:?}", heap) to show the heap after the bubble up operation.

DSA Rust

let mut heap = vec![100, 50, 30, 20, 40];
let new_value = 60;
heap.push(new_value);

let mut index = heap.len() - 1;
while index > 0 {
    let parent_index = (index - 1) / 2;
    if heap[index] > heap[parent_index] {
        heap.swap(index, parent_index);
        index = parent_index;
    } else {
        break;
    }
}

// Print the heap vector
# Your code here

Hint

Use println!("{:?}", heap); to print the vector.

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