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.

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