Heap Insert Operation Bubble Up in DSA C++ - Execution Trace

Concept Flow - Heap Insert Operation Bubble Up

Insert new element at end of array

↓

Compare with parent node

↓

Swap with parent

↓

Move to parent's index

↓

Repeat compare with new parent

↓

Done

Insert the new element at the end, then repeatedly swap it with its parent if smaller, moving up until heap property is restored.

Execution Sample

DSA C++

void bubbleUp(vector<int>& heap, int index) {
  while (index > 0) {
    int parent = (index - 1) / 2;
    if (heap[index] < heap[parent]) {
      swap(heap[index], heap[parent]);
      index = parent;
    } else {
      break;
    }
  }
}

This code performs bubble up after a new element has been inserted at the end of a min-heap (e.g., via push_back). It swaps the element at 'index' with its parent if smaller, repeating until heap property is restored.

Execution Table

Step	Operation	Index	Parent Index	Heap Array State	Pointer Changes	Visual State
1	Insert 8 at end	7	N/A	[10, 15, 30, 40, 50, 100, 40, 8]	New element index = 7	Array: [10, 15, 30, 40, 50, 100, 40, 8] Tree: 10 / \ 15 30 / \ / \ 40 50 100 40 \ 8 (new)
2	Compare with parent	7	3	[10, 15, 30, 40, 50, 100, 40, 8]	Compare heap[7]=8 with heap[3]=40	8 < 40 → swap
3	Swap with parent	7 → 3	1	[10, 15, 30, 8, 50, 100, 40, 40]	Swap indices 7 and 3, index now 3	Array: [10, 15, 30, 8, 50, 100, 40, 40] Tree: 10 / \ 15 30 / \ / \ 8 50 100 40 (40 moved down)
4	Compare with parent	3	1	[10, 15, 30, 8, 50, 100, 40, 40]	Compare heap[3]=8 with heap[1]=15	8 < 15 → swap
5	Swap with parent	3 → 1	0	[10, 8, 30, 15, 50, 100, 40, 40]	Swap indices 3 and 1, index now 1	Array: [10, 8, 30, 15, 50, 100, 40, 40] Tree: 10 / \ 8 30 / \ / \ 15 50 100 40
6	Compare with parent	1	0	[10, 8, 30, 15, 50, 100, 40, 40]	Compare heap[1]=8 with heap[0]=10	8 < 10 → swap
7	Swap with parent	1 → 0	N/A	[8, 10, 30, 15, 50, 100, 40, 40]	Swap indices 1 and 0, index now 0	Array: [8, 10, 30, 15, 50, 100, 40, 40] Tree: 8 / \ 10 30 / \ / \ 15 50 100 40
8	Compare with parent	0	N/A	[8, 10, 30, 15, 50, 100, 40, 40]	Index 0 is root, stop bubble up	Heap property restored

💡 Index reached root (0), no parent to compare, bubble up stops

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	Final
index	N/A	7	3	1	0	0
heap array	[10, 15, 30, 40, 50, 100, 40]	[10, 15, 30, 40, 50, 100, 40, 8]	[10, 15, 30, 8, 50, 100, 40, 40]	[10, 8, 30, 15, 50, 100, 40, 40]	[8, 10, 30, 15, 50, 100, 40, 40]	[8, 10, 30, 15, 50, 100, 40, 40]

Key Moments - 3 Insights

Why do we compare the new element with its parent instead of children during bubble up?

Because bubble up moves the new element up the tree to restore heap order. We only compare with the parent to check if the new element is smaller and needs to move up. This is shown in execution_table steps 2, 4, and 6 where comparisons happen only with parents.

What happens when the new element reaches the root during bubble up?

When the index becomes 0, it means the element is at the root and has no parent to compare with. The bubble up stops here as shown in execution_table step 8.

Why do we swap elements during bubble up?

Swapping moves the smaller element up to maintain the min-heap property. Without swapping, the heap property would be violated. This is seen in steps 3, 5, and 7 where swaps happen to move the new element up.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the heap array state after the swap?

A [10, 8, 30, 15, 50, 100, 40, 40]

B [10, 15, 30, 8, 50, 100, 40, 40]

C [8, 10, 30, 15, 50, 100, 40, 40]

D [10, 15, 30, 40, 50, 100, 40, 8]

💡 Hint

Check the 'Heap Array State' column in execution_table row for step 5.

At which step does the bubble up operation stop?

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

Look for the step where index is 0 and no parent exists in execution_table.

If the inserted element was 35 instead of 8, how would the bubble up change?

A It would swap multiple times up to the root.

B It would swap once and then stop.

C It would not swap at all and stop immediately.

D It would swap with all children nodes.

💡 Hint

35 < 40 (parent at index 3, see step 2) so swaps once to index 3; then 35 > 15 (parent at index 1, see step 4) so stops.

Concept Snapshot

Heap Insert Bubble Up:
- Insert new element at end of heap array
- Compare with parent node
- If smaller, swap and move up
- Repeat until root or no swap needed
- Restores min-heap property efficiently

Full Transcript

This visualization shows how a new element is inserted at the end of a min-heap array and then moved up by swapping with its parent nodes if it is smaller. The process repeats until the element reaches the root or no parent is larger. Each step updates the heap array and the tree structure, maintaining the heap property. Key moments include understanding why comparisons are only with parents, what happens at the root, and why swaps are necessary. The quiz tests understanding of heap states at various steps and the stopping condition.