Heap Insert Operation Bubble Up in DSA Python - Execution Trace

Concept Flow - Heap Insert Operation Bubble Up

Insert new element at end of array

↓

Compare with parent element

↓

Swap with parent

↓

Move pointer to parent

↩Back to Compare

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 Python

heap = [10, 15, 30, 40, 50, 100, 40]
new_val = 8
heap.append(new_val)
index = len(heap) - 1
while index > 0 and heap[index] < heap[(index - 1) // 2]:
    parent = (index - 1) // 2
    heap[index], heap[parent] = heap[parent], heap[index]
    index = parent

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

Execution Table

Step	Operation	Index	Parent Index	Heap Array State	Pointer Movement	Visual State
1	Insert 8 at end	7	-	[10, 15, 30, 40, 50, 100, 40, 8]	New node at index 7	Array: [10, 15, 30, 40, 50, 100, 40, 8]
2	Compare with parent	7	3	Same	Compare 8 with 40 at index 3	8 < 40 → swap needed
3	Swap with parent	7→3	3	[10, 15, 30, 8, 50, 100, 40, 40]	Swap indices 7 and 3	After swap: [10, 15, 30, 8, 50, 100, 40, 40]
4	Move pointer to parent	3	-	Same	Pointer moves to index 3	Current node is 8 at index 3
5	Compare with parent	3	1	Same	Compare 8 with 15 at index 1	8 < 15 → swap needed
6	Swap with parent	3→1	1	[10, 8, 30, 15, 50, 100, 40, 40]	Swap indices 3 and 1	After swap: [10, 8, 30, 15, 50, 100, 40, 40]
7	Move pointer to parent	1	-	Same	Pointer moves to index 1	Current node is 8 at index 1
8	Compare with parent	1	0	Same	Compare 8 with 10 at index 0	8 < 10 → swap needed
9	Swap with parent	1→0	0	[8, 10, 30, 15, 50, 100, 40, 40]	Swap indices 1 and 0	After swap: [8, 10, 30, 15, 50, 100, 40, 40]
10	Move pointer to parent	0	-	Same	Pointer moves to index 0	Current node is 8 at root
11	Compare with parent	0	-	Same	No parent (root node)	Stop bubbling up
12	End	-	-	[8, 10, 30, 15, 50, 100, 40, 40]	-	Final heap after insert and bubble up

💡 Pointer reached root or no swap needed; heap property restored.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 6	After Step 9	Final
heap	[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]
index	-	7	3	1	0	0
parent	-	-	3	1	0	-

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 swap. This is shown in execution_table steps 2, 5, and 8.

What happens if the new element is not smaller than its parent?

The bubble up stops immediately because the heap property is satisfied. This is shown in execution_table step 11 where no parent swap is needed and the process ends.

Why do we stop when the pointer reaches index 0?

Index 0 is the root node and has no parent. We cannot bubble up further. This is shown in execution_table step 10 and 11 where the pointer moves to root and stops.

Visual Quiz - 3 Questions

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

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

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

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

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

💡 Hint

Check the 'Heap Array State' column at step 6 in the execution_table.

At which step does the pointer reach the root node (index 0)?

A Step 9

B Step 10

C Step 7

D Step 11

💡 Hint

Look at the 'Pointer Movement' and 'Index' columns in execution_table steps 9 and 10.

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

A It would swap once and then stop.

B It would stop immediately after insertion.

C It would bubble up all the way to root.

D It would swap twice and then stop.

💡 Hint

Refer to the comparison steps in execution_table where swaps happen only if new element is smaller than parent.

Concept Snapshot

Heap Insert Bubble Up:
- Insert new element at end of heap array
- Compare with parent: if smaller, swap
- Move pointer to parent and repeat
- Stop when root reached 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 and then bubbling it up. The new element is compared with its parent, and if smaller, they swap. This process repeats moving the pointer up until the heap property is restored or the root is reached. The execution table tracks each step, showing the heap array state and pointer movements. Key moments clarify why comparisons are with parents and when the process stops. The quiz tests understanding of heap states and pointer positions during bubble up.

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 smaller than its parent

B. To remove the smallest element from the heap

C. To sort all elements in the heap in ascending order

D. To add a new element at the bottom without any changes

Solution

1. Step 1: Understand heap property

   In a min-heap, every parent node is smaller than its children.

2. Step 2: Purpose of bubble up

   When a new element is added at the bottom, bubble up moves it up if it is smaller than its parent to restore 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 A

4. Quick Check:

   Bubble up fixes heap order by moving smaller elements up [OK]

Hint: Bubble up moves smaller new elements up to fix heap [OK]

Common Mistakes:

• Thinking bubble up sorts the entire heap
• Confusing bubble up with removing elements
• Assuming bubble up adds element without changes

2. Which of the following Python code snippets correctly performs the bubble up step after inserting a new element at the end of a min-heap list heap?

easy

A. while i > 0 and heap[i] < heap[(i - 1) // 2]: heap[i], heap[(i - 1) // 2] = heap[(i - 1) // 2], heap[i]; i = (i - 1) // 2

B. while i > 0 and heap[i] > heap[(i - 1) // 2]: heap[i], heap[(i - 1) // 2] = heap[(i - 1) // 2], heap[i]; i = (i - 1) // 2

C. for i in range(len(heap)): if heap[i] < heap[(i - 1) // 2]: swap(heap[i], heap[(i - 1) // 2])

D. if heap[i] < heap[i + 1]: swap(heap[i], heap[i + 1])

Solution

1. Step 1: Identify bubble up condition

   Bubble up swaps while current element is smaller than its parent.

2. Step 2: Check code correctness

   while i > 0 and heap[i] < heap[(i - 1) // 2]: heap[i], heap[(i - 1) // 2] = heap[(i - 1) // 2], heap[i]; i = (i - 1) // 2 uses a while loop with condition heap[i] < heap[parent], swapping and updating i correctly.

3. Final Answer:

   while i > 0 and heap[i] < heap[(i - 1) // 2]: heap[i], heap[(i - 1) // 2] = heap[(i - 1) // 2], heap[i]; i = (i - 1) // 2 -> Option A

4. Quick Check:

   Bubble up swaps smaller child with parent [OK]

Hint: Bubble up swaps while child < parent using index (i-1)//2 [OK]

Common Mistakes:

• Using > instead of < in condition
• Using for loop instead of while
• Swapping with wrong indices

3. Given the min-heap represented as a list heap = [2, 5, 8, 10, 15], what will be the heap list after inserting 1 and performing bubble up?

medium

A. [1, 2, 5, 10, 15, 8]

B. [1, 2, 8, 10, 15, 5]

C. [2, 5, 8, 10, 15, 1]

D. [1, 5, 2, 10, 15, 8]

Solution

1. Step 1: Insert 1 at the end

   Heap becomes [2, 5, 8, 10, 15, 1].

2. Step 2: Bubble up 1

   Compare 1 with parent at index 2 (value 8). Swap: [2, 5, 1, 10, 15, 8]. Then compare 1 with new parent at index 0 (value 2). Swap: [1, 5, 2, 10, 15, 8].

3. Final Answer:

   [1, 5, 2, 10, 15, 8] -> Option D

4. Quick Check:

   Inserted 1 bubbled up to root [OK]

Hint: Insert at end, swap up while smaller than parent [OK]

Common Mistakes:

• Not swapping enough times
• Swapping with wrong parent index
• Leaving new element at the end

4. The following code attempts to insert a new element into a min-heap and bubble it up, but it has a bug. What is the error?

def insert(heap, val):
    heap.append(val)
    i = len(heap) - 1
    while i > 0 and heap[i] > heap[(i - 1) // 2]:
        heap[i], heap[(i - 1) // 2] = heap[(i - 1) // 2], heap[i]
        i = (i - 1) // 2

medium

A. The append method should be insert at index 0

B. The index update i = (i - 1) // 2 is incorrect

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

D. The while loop condition should check i >= 0 instead of i > 0

Solution

1. Step 1: Analyze bubble up condition

   For 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

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

3. Final Answer:

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

4. Quick Check:

   Bubble up swaps when child < parent [OK]

Hint: Use '<' to bubble up smaller elements in min-heap [OK]

Common Mistakes:

• Using '>' instead of '<' in condition
• Incorrect index updates
• Appending at wrong position

5. You have a max-heap represented as [90, 70, 80, 40, 50, 60]. You insert 85 at the end and perform bubble up. What will be the final heap list?

hard

A. [90, 85, 80, 70, 50, 60, 40]

B. [90, 70, 85, 40, 50, 60, 80]

C. [85, 70, 90, 40, 50, 60, 80]

D. [90, 70, 80, 40, 50, 60, 85]

Solution

1. Step 1: Insert 85 at the end

   Heap becomes [90, 70, 80, 40, 50, 60, 85].

2. Step 2: Bubble up 85 in max-heap

   Compare 85 with parent at index 2 (80). Since 85 > 80, swap: [90, 70, 85, 40, 50, 60, 80]. Then compare 85 with new parent at index 0 (90). 85 < 90, stop bubbling up.

3. Final Answer:

   [90, 70, 85, 40, 50, 60, 80] -> Option B

4. Quick Check:

   Bubble up swaps larger child with parent in max-heap [OK]

Hint: In max-heap, bubble up swaps if child > parent [OK]

Common Mistakes:

• Not swapping enough times
• Confusing min-heap and max-heap conditions
• Leaving new element at the end