Heap Insert Operation Bubble Up in DSA C++ - Build from Scratch

Heap Insert Operation Bubble Up

📖 Scenario: You are managing a priority queue for tasks using a min-heap. When a new task with a priority value is added, it must be placed correctly to keep the heap property intact.

🎯 Goal: Build a min-heap insert operation that adds a new element and uses bubble up to restore heap order.

📋 What You'll Learn

Create a vector called heap with initial values {10, 15, 20, 17, 25}

Create an integer variable called newValue and set it to 8

Write code to insert newValue at the end of heap and bubble it up to maintain min-heap order

Print the final state of heap after insertion

💡 Why This Matters

🌍 Real World

Priority queues are used in task scheduling, network routing, and event simulation where the smallest or highest priority item must be accessed quickly.

💼 Career

Understanding heap insertions and bubble up is essential for software engineers working on performance-critical applications, databases, and real-time systems.

1

Create the initial heap vector

Create a std::vector<int> called heap with these exact values: {10, 15, 20, 17, 25}

DSA C++

# Your code here

Hint

Use std::vector<int> and initialize it with the given values.

2

Add the new value to insert

Create an integer variable called newValue and set it to 8

DSA C++

#include 
#include 

int main() {
    std::vector heap = {10, 15, 20, 17, 25};
    // Your code here
}

Hint

Declare int newValue = 8; inside main().

3

Insert and bubble up the new value

Insert newValue at the end of heap using push_back. Then use a while loop with variables index and parent to bubble up the new value until the min-heap property is restored.

DSA C++

#include 
#include 

int main() {
    std::vector heap = {10, 15, 20, 17, 25};
    int newValue = 8;
    // Your code here
}

Hint

Use push_back to add newValue. Then bubble up by swapping with parent while smaller.

4

Print the heap after insertion

Use a for loop with variable val to print all elements of heap separated by spaces on one line.

DSA C++

#include 
#include 

int main() {
    std::vector heap = {10, 15, 20, 17, 25};
    int newValue = 8;
    heap.push_back(newValue);
    int index = heap.size() - 1;
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap[parent] <= heap[index]) {
            break;
        }
        std::swap(heap[parent], heap[index]);
        index = parent;
    }
    // Your code here
}

Hint

Print all elements in heap separated by spaces on one line.

Practice

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

easy

A. To delete the root element of the heap

B. To move the new element to the bottom of the heap

C. To restore the heap property by moving the new element up if it is smaller than its parent

D. To sort all elements in ascending order

Solution

1. Step 1: Understand heap property

   In a min-heap, every parent node is smaller than its children. When inserting, this property might be violated.

2. Step 2: Purpose of bubble up

   The bubble up operation moves the newly inserted element up the tree if it is smaller than its parent, restoring the heap property.

3. Final Answer:

   To restore the heap property by moving the new element up if it is smaller than its parent -> Option C

4. Quick Check:

   Bubble up fixes heap by moving smaller element up [OK]

Hint: Bubble up moves smaller new element up to fix heap [OK]

Common Mistakes:

• Thinking bubble up moves element down
• Confusing bubble up with deletion
• Assuming bubble up sorts entire heap

2. Which of the following C++ code snippets correctly performs the bubble up step after inserting a new element at the end of a min-heap vector heap?

easy

A. int i = heap.size() - 1; while (i > 0 && heap[i] < heap[(i - 1) / 2]) { std::swap(heap[i], heap[(i - 1) / 2]); i = (i - 1) / 2; }

B. int i = 0; while (i < heap.size() && heap[i] > heap[(2 * i) + 1]) { std::swap(heap[i], heap[(2 * i) + 1]); i = (2 * i) + 1; }

C. int i = heap.size() - 1; while (i > 0 && heap[i] > heap[(i - 1) / 2]) { std::swap(heap[i], heap[(i - 1) / 2]); i = (i - 1) / 2; }

D. int i = heap.size() - 1; while (i > 0 && heap[i] < heap[(2 * i) + 2]) { std::swap(heap[i], heap[(2 * i) + 2]); i = (2 * i) + 2; }

Solution

1. Step 1: Identify bubble up logic

   Bubble up compares the inserted element with its parent at index (i-1)/2 and swaps if smaller.

2. Step 2: Check each option

   int i = heap.size() - 1; while (i > 0 && heap[i] < heap[(i - 1) / 2]) { std::swap(heap[i], heap[(i - 1) / 2]); i = (i - 1) / 2; } correctly uses the parent index and swaps while the child is smaller. Others use wrong indices or wrong comparison.

3. Final Answer:

   int i = heap.size() - 1; while (i > 0 && heap[i] < heap[(i - 1) / 2]) { std::swap(heap[i], heap[(i - 1) / 2]); i = (i - 1) / 2; } -> Option A

4. Quick Check:

   Bubble up uses parent index (i-1)/2 and swaps if smaller [OK]

Hint: Parent index = (i-1)/2; swap if child smaller [OK]

Common Mistakes:

• Using child indices instead of parent
• Swapping when child is larger
• Starting index at 0 instead of last element

3. Given the min-heap represented by the vector heap = {2, 5, 8, 10, 15}, what will be the heap vector after inserting 1 and performing bubble up?

medium

A. [1, 2, 8, 10, 15, 5]

B. [1, 2, 5, 10, 15, 8]

C. [1, 5, 2, 10, 15, 8]

D. [2, 5, 8, 10, 15, 1]

Solution

1. Step 1: Insert 1 at the end

   Heap becomes [2, 5, 8, 10, 15, 1]. Index of 1 is 5.

2. Step 2: Bubble up 1

   Parent index = (5-1)/2 = 2. Compare heap[5]=1 with heap[2]=8. Since 1 < 8, swap. Heap: [2, 5, 1, 10, 15, 8]. Now i=2.

3. Step 3: Continue bubble up

   Parent index = (2-1)/2=0. Compare heap[2]=1 with heap[0]=2. Since 1 < 2, swap. Heap: [1, 5, 2, 10, 15, 8]. Now i=0, stop.

4. Final Answer:

   [1, 5, 2, 10, 15, 8] -> Option B

5. Quick Check:

   Bubble up swaps until heap property restored [OK]

Hint: Insert at end, swap with parent if smaller until root [OK]

Common Mistakes:

• Not swapping enough times
• Swapping with wrong parent index
• Leaving new element at the end

4. Consider the following code snippet for bubble up after inserting into a min-heap vector heap. Identify the error:

int i = heap.size() - 1;
while (i > 0 && heap[i] > heap[(i - 1) / 2]) {
    std::swap(heap[i], heap[(i - 1) / 2]);
    i = (i - 1) / 2;
}

medium

A. The comparison operator should be '<' instead of '>'

B. The loop should start from i = 0

C. The swap function is used incorrectly

D. The parent index calculation is wrong

Solution

1. Step 1: Understand bubble up condition

   In a min-heap, bubble up swaps when child is smaller than parent, so condition should be heap[i] < heap[parent].

2. Step 2: Identify error in code

   The code uses heap[i] > heap[parent], which is incorrect and will not restore min-heap property.

3. Final Answer:

   The comparison operator should be '<' instead of '>' -> Option A

4. Quick Check:

   Bubble up swaps when child < parent [OK]

Hint: Bubble up swaps if child smaller than parent [OK]

Common Mistakes:

• Using wrong comparison direction
• Starting loop at wrong index
• Miscalculating parent index

5. You have a max-heap represented by heap = {20, 15, 18, 10, 12, 17}. You insert 19 at the end and perform bubble up. What is the resulting heap vector?

hard

A. [20, 15, 18, 10, 12, 17, 19]

B. [20, 19, 18, 15, 12, 17, 10]

C. [19, 15, 20, 10, 12, 17, 18]

D. [20, 15, 19, 10, 12, 17, 18]

Solution

1. Step 1: Insert 19 at the end

   Heap becomes [20, 15, 18, 10, 12, 17, 19]. Index of 19 is 6.

2. Step 2: Bubble up 19 in max-heap

   Parent index = (6-1)/2 = 2. Compare heap[6]=19 with heap[2]=18. Since 19 > 18, swap. Heap: [20, 15, 19, 10, 12, 17, 18]. Now i=2.

3. Step 3: Continue bubble up

   Parent index = (2-1)/2=0. Compare heap[2]=19 with heap[0]=20. Since 19 < 20, stop.

4. Final Answer:

   [20, 15, 19, 10, 12, 17, 18] -> Option D

5. Quick Check:

   Bubble up swaps if child > parent in max-heap [OK]

Hint: In max-heap, bubble up swaps if child bigger than parent [OK]

Common Mistakes:

• Using min-heap logic for max-heap
• Not swapping enough times
• Incorrect parent index calculation