Heap Insert Operation Bubble Up in DSA C++

Mental Model

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

Analogy: Imagine a new player joining a line for a game where the tallest players stand in front. The new player joins at the back and moves forward until no one taller is in front.

Heap as array: [10, 15, 20, 17, 25]
Insert 13 at end: [10, 15, 20, 17, 25, 13]
Positions: index 0↑10, 1↑15, 2↑20, 3↑17, 4↑25, 5↑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: Insert 13 at the end of the heap array

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

Why: New value must be added at the last position before fixing heap

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

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

Why: Heap is a min-heap; smaller values must be higher, so bubble up 13

Step 3: Compare 13 with its new parent 10 at index 0; since 13 > 10, stop bubbling up

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

Why: Heap property restored; parent is smaller, so no more swaps

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

class MinHeap {
public:
    vector<int> heap;

    void insert(int val) {
        heap.push_back(val); // add at end
        bubbleUp(heap.size() - 1); // fix heap
    }

    void bubbleUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[index] < heap[parent]) {
                swap(heap[index], heap[parent]); // swap smaller up
                index = parent; // move up to parent
            } else {
                break; // heap property restored
            }
        }
    }

    void printHeap() {
        for (int val : heap) {
            cout << val << " ";
        }
        cout << endl;
    }
};

int main() {
    MinHeap h;
    h.heap = {10, 15, 20, 17, 25};
    h.insert(13);
    h.printHeap();
    return 0;
}

heap.push_back(val); // add at end

Add new value at the last position in the heap array

bubbleUp(heap.size() - 1); // fix heap

Start bubbling up from the newly added element's index

while (index > 0) {

Continue bubbling up until we reach the root

int parent = (index - 1) / 2;

Find parent index of current node

if (heap[index] < heap[parent]) {

Check if current node is smaller than parent to maintain min-heap

swap(heap[index], heap[parent]); // swap smaller up

Swap current node with parent to move smaller value up

index = parent; // move up to parent

Update index to parent's position to continue bubbling up

else { break; }

Stop bubbling up if heap property is satisfied

Output

10 15 13 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 we only use a few extra variables for swapping and indexing

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 added as root with no bubbling needed

DSA C++

while (index > 0) {

Insert value larger than all existing values

Value stays at the end, no swaps occur

DSA C++

if (heap[index] < heap[parent]) {

Insert value smaller than root

Value bubbles all the way up to root

DSA C++

index = parent;

When to Use This Pattern

When you need to add a new element to a heap and keep it ordered, use bubble up to fix the heap from bottom to top.

Common Mistakes

Mistake: Not updating the index after swapping during bubble up
Fix: Set index = parent after swap to continue bubbling up correctly

Mistake: Comparing with wrong parent index or off-by-one errors
Fix: Calculate parent as (index - 1) / 2 carefully for zero-based arrays

Summary

It inserts a new value into a heap and moves it up until the heap order is correct.

Use it when adding elements to a heap to keep the heap property intact.

The key is to add at the end and swap upwards until the parent is smaller or equal.

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