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.