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 new element with parent

↓

Swap with parent

↓

Move pointer to parent

↩Back to compare step

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

Execution Sample

DSA C

int heap[] = {10, 15, 30, 40, 50, 100, 40};
int size = 7;
int new_val = 8;
heap[size] = new_val;
size++;
bubbleUp(heap, size - 1);

Insert 8 into min-heap and bubble it up to restore heap order.

Execution Table

Step	Operation	Index	Parent Index	Array State	Pointer Movement	Visual State
1	Insert 8 at end	7	3	[10, 15, 30, 40, 50, 100, 40, 8]	Pointer at index 7	Array: [10, 15, 30, 40, 50, 100, 40, 8] Tree: 10 / \ 15 30 / \ / \ 40 50 100 40 / 8 ← new node
2	Compare with parent	7	3	[10, 15, 30, 40, 50, 100, 40, 8]	8 < 40? Yes, swap	Swap nodes at index 7 and 3
3	Swap with parent	7 → 3	1	[10, 15, 30, 8, 50, 100, 40, 40]	Pointer moves to index 3	Array: [10, 15, 30, 8, 50, 100, 40, 40] Tree: 10 / \ 15 30 / \ / \ 8 50 100 40 / 40
4	Compare with parent	3	1	[10, 15, 30, 8, 50, 100, 40, 40]	8 < 15? Yes, swap	Swap nodes at index 3 and 1
5	Swap with parent	3 → 1	0	[10, 8, 30, 15, 50, 100, 40, 40]	Pointer moves to index 1	Array: [10, 8, 30, 15, 50, 100, 40, 40] Tree: 10 / \ 8 30 / \ / \ 15 50 100 40 / 40
6	Compare with parent	1	0	[10, 8, 30, 15, 50, 100, 40, 40]	8 < 10? Yes, swap	Swap nodes at index 1 and 0
7	Swap with parent	1 → 0	-	[8, 10, 30, 15, 50, 100, 40, 40]	Pointer moves to index 0 (root)	Array: [8, 10, 30, 15, 50, 100, 40, 40] Tree: 8 / \ 10 30 / \ / \ 15 50 100 40 / 40
8	Compare with parent	0	-	[8, 10, 30, 15, 50, 100, 40, 40]	At root, stop bubble up	Bubble up complete

💡 Pointer reached root at index 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
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]
pointer index	-	7	3	1	0	0
parent index	-	3	1	0	-	-

Key Moments - 3 Insights

Why do we swap the new element with its parent only if it is smaller?

Because in a min-heap, the parent must always be smaller or equal to its children. Swapping only when the new element is smaller restores this property, as shown in steps 2, 4, and 6 of the execution_table.

What happens when the pointer reaches the root during bubble up?

When the pointer reaches index 0 (the root), there is no parent to compare with, so the bubble up stops. This is shown in step 8 where the pointer is at root and bubble up ends.

Why do we insert the new element at the end of the array first?

Because the heap is a complete binary tree represented as an array, new elements are always added at the next available position at the end to maintain completeness before fixing order by bubbling up, as shown in step 1.

Visual Quiz - 3 Questions

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

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

B [10, 8, 30, 15, 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 'Array State' column at step 5 in the execution_table.

At which step does the pointer reach the root and bubble up stops?

A Step 8

B Step 7

C Step 6

D Step 5

💡 Hint

Look at the 'Pointer Movement' and 'Operation' columns in the execution_table for when pointer is at index 0 and stops.

If the new element was 20 instead of 8, how would the bubble up process change?

A It would swap once before stopping.

B It would swap twice before stopping.

C No swaps would occur; bubble up stops immediately.

D It would bubble up to the root.

💡 Hint

Compare the new element with parents in the execution_table; 20 is larger than 15, so no swaps.

Concept Snapshot

Heap Insert Bubble Up:
- Insert new element at array end
- Compare with parent index = (i-1)/2
- If new < parent, swap and move pointer up
- Repeat until root or no swap needed
- Restores min-heap property efficiently

Full Transcript

This visual trace shows how inserting a new element into a min-heap works by adding it at the end of the array and then bubbling it up. The bubble up compares the new element with its parent and swaps if the new element is smaller, moving the pointer up the tree. This continues until the new element is at the root or no swap is needed, restoring the heap property. The execution table tracks each step, showing array states and pointer movements. Key moments clarify why swaps happen only when smaller and why insertion is at the end. The quiz tests understanding of array states and stopping conditions.

Practice

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

easy

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

B. To remove the smallest element from the heap

C. To sort all elements in ascending order

D. To swap the root with the last element

Solution

1. Step 1: Understand heap property

   A max-heap requires each parent to be greater than or equal to its children.

2. Step 2: Purpose of bubble up

   When inserting, bubble up moves the new element up if it is larger than its parent to restore heap property.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Thinking bubble up sorts the entire heap
• Confusing bubble up with removing elements
• Assuming bubble up swaps root with last element

2. Which of the following C code snippets correctly performs the bubble up step after inserting a new element at index i in a max-heap array heap?

easy

A. if (heap[i] > heap[i + 1]) swap(heap[i], heap[i + 1]);

B. while (i > 0 && heap[i] < heap[(i - 1) / 2]) { int temp = heap[i]; heap[i] = heap[(i - 1) / 2]; heap[(i - 1) / 2] = temp; i = (i - 1) / 2; }

C. for (int j = i; j > 0; j--) { if (heap[j] > heap[j - 1]) swap(heap[j], heap[j - 1]); }

D. while (i > 0 && heap[i] > heap[(i - 1) / 2]) { int temp = heap[i]; heap[i] = heap[(i - 1) / 2]; heap[(i - 1) / 2] = temp; i = (i - 1) / 2; }

Solution

1. Step 1: Identify correct bubble up condition

   Bubble up swaps while current element is greater than its parent at index (i-1)/2.

2. Step 2: Check code correctness

   while (i > 0 && heap[i] > heap[(i - 1) / 2]) { int temp = heap[i]; heap[i] = heap[(i - 1) / 2]; heap[(i - 1) / 2] = temp; i = (i - 1) / 2; } correctly uses a while loop with condition and swaps elements, updating index i to parent.

3. Final Answer:

   while (i > 0 && heap[i] > heap[(i - 1) / 2]) { int temp = heap[i]; heap[i] = heap[(i - 1) / 2]; heap[(i - 1) / 2] = temp; i = (i - 1) / 2; } -> Option D

4. Quick Check:

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

Hint: Use parent index (i-1)/2 and swap if child > parent [OK]

Common Mistakes:

• Using < instead of > in condition
• Using for loop instead of while
• Swapping with next element instead of parent

3. Given the max-heap array heap = [50, 30, 40, 10, 20], what will be the heap array after inserting 45 and performing bubble up?

medium

A. [50, 45, 40, 10, 20, 30]

B. [50, 30, 45, 10, 20, 40]

C. [45, 30, 50, 10, 20, 40]

D. [50, 30, 40, 10, 20, 45]

Solution

1. Step 1: Insert 45 at the end

   Insert 45 at index 5: heap = [50, 30, 40, 10, 20, 45]

2. Step 2: Bubble up 45

   Parent of index 5 is (5-1)/2=2 with value 40. Since 45 > 40, swap them. New heap: [50, 30, 45, 10, 20, 40]

3. Final Answer:

   [50, 30, 45, 10, 20, 40] -> Option B

4. Quick Check:

   Inserted 45 bubbled up swapping with 40 [OK]

Hint: Insert at end, swap up if bigger than parent [OK]

Common Mistakes:

• Not swapping after insertion
• Swapping with wrong parent index
• Placing 45 at wrong position

4. Consider the following bubble up code snippet for a max-heap insert:

while (i > 0 && heap[i] < heap[(i - 1) / 2]) {
    int temp = heap[i];
    heap[i] = heap[(i - 1) / 2];
    heap[(i - 1) / 2] = temp;
    i = (i - 1) / 2;
}

What is the error in this code?

medium

A. Parent index calculation is incorrect

B. The loop should start from i = 1 instead of i > 0

C. The comparison operator should be > instead of < to maintain max-heap property

D. Swapping elements is not needed in bubble up

Solution

1. Step 1: Analyze comparison operator

   Bubble up in max-heap swaps when child is greater than parent, so condition should be heap[i] > heap[parent].

2. Step 2: Identify error

   Code uses heap[i] < heap[parent], which is wrong and breaks max-heap property.

3. Final Answer:

   The comparison operator should be > instead of < to maintain max-heap property -> Option C

4. Quick Check:

   Max-heap bubble up swaps if child > parent [OK]

Hint: Use > to compare child and parent in max-heap bubble up [OK]

Common Mistakes:

• Using < instead of > in condition
• Incorrect parent index formula
• Skipping swaps in bubble up

5. You have a max-heap represented as an array: [60, 40, 55, 20, 30, 50]. You insert 65 at the end and perform bubble up. What is the final heap array after bubble up completes?

hard

A. [65, 60, 55, 20, 30, 50, 40]

B. [65, 40, 60, 20, 30, 50, 55]

C. [60, 40, 65, 20, 30, 50, 55]

D. [60, 40, 55, 20, 30, 50, 65]

Solution

1. Step 1: Insert 65 at the end

   Heap becomes [60, 40, 55, 20, 30, 50, 65]. Index of 65 is 6.

2. Step 2: Bubble up 65

   Parent index = (6-1)/2 = 2, value 55. Since 65 > 55, swap: [60, 40, 65, 20, 30, 50, 55].

3. Step 3: Continue bubble up

   New index = 2. Parent index = (2-1)/2 = 0, value 60. Since 65 > 60, swap: [65, 40, 60, 20, 30, 50, 55].

4. Final Answer:

   [65, 60, 55, 20, 30, 50, 40] -> Option A

5. Quick Check:

   Inserted 65 bubbled up swapping with 55 then 60 [OK]

Hint: Bubble up swaps repeatedly until parent is larger [OK]

Common Mistakes:

• Stopping bubble up after one swap
• Swapping with wrong parent index
• Not updating index after swap