Heap Insert Operation Bubble Up in DSA Python

Mental Model

When adding a new number to a heap, we place it at the end and then move it up until the heap rules are true again.

Analogy: Imagine adding a new player to a team lineup where the best players stand at the front. You add the new player at the end and then let them move forward if they are better than the player in front of them.

Heap as array:
[10, 15, 20, 17, 25]
Insert 13 at end:
[10, 15, 20, 17, 25, 13]
Index positions:
[0,  1,  2,  3,  4,  5]

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: Add 13 at the end of the heap array

[10, 15, 20, 17, 25, 13]

Why: New value must be added at the end before fixing the 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 property violated, smaller child must move up

Step 3: Compare 13 with new parent 10 at index 0; since 13 > 10, stop bubbling up

[10, 15, 13, 17, 25, 20]

Why: Heap property restored, no more swaps needed

Result:

[10, 15, 13, 17, 25, 20]

Annotated Code

DSA Python

class MinHeap:
    def __init__(self):
        self.heap = []

    def insert(self, val):
        self.heap.append(val)  # add at end
        self._bubble_up(len(self.heap) - 1)  # fix heap

    def _bubble_up(self, index):
        while index > 0:
            parent = (index - 1) // 2
            if self.heap[index] < self.heap[parent]:
                self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]  # swap
                index = parent  # move up
            else:
                break  # heap property restored

    def __str__(self):
        return ' -> '.join(str(x) for x in self.heap) + ' -> null'

# Driver code
heap = MinHeap()
for val in [10, 15, 20, 17, 25]:
    heap.insert(val)
heap.insert(13)  # insert new value
print(heap)

self.heap.append(val) # add at end

Add new value at the end of the heap array

self._bubble_up(len(self.heap) - 1) # fix heap

Start bubbling up from the last index to restore heap property

parent = (index - 1) // 2

Calculate parent index of current node

if self.heap[index] < self.heap[parent]:

Check if current node is smaller than parent to decide swap

self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index] # swap

Swap child and parent to move smaller value up

index = parent # move up

Update index to parent's position to continue bubbling up

else: break # heap property restored

Stop bubbling up when heap property is satisfied

Output

10 -> 15 -> 13 -> 17 -> 25 -> 20 -> null

Complexity Analysis

Time: O(log n) because in worst case the new element moves up the height of the heap

Space: O(1) because insertion and bubbling up happen in place without extra space

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 the root without bubbling up

DSA Python

while index > 0:

Insert value larger than all existing values

Value stays at the end, no swaps needed

DSA Python

else:
    break  # heap property restored

Insert value smaller than root

Value bubbles all the way up to root

DSA Python

index = parent  # move up

When to Use This Pattern

When you see a problem asking to add an element to a heap and keep it valid, use bubble up to restore order efficiently.

Common Mistakes

Mistake: Not swapping with parent when child is smaller, breaking heap property
Fix: Add condition to compare child and parent and swap if child is smaller

Mistake: Continuing to bubble up even after heap property is restored
Fix: Break the loop when no swap is needed

Mistake: Calculating parent index incorrectly
Fix: Use parent = (index - 1) // 2 for zero-based arrays

Summary

It inserts a new value into a min-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 insight is that only the path from the inserted node to the root needs fixing by swapping upwards.

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