Heap Insert Operation Bubble Up in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the heap array after inserting 15?

Given a min-heap represented as an array, what is the state of the heap array after inserting the value 15 and performing bubble up?

DSA Python

heap = [10, 20, 30, 40, 50]

# Insert 15
heap.append(15)

# Bubble up operation
index = len(heap) - 1
while index > 0:
    parent = (index - 1) // 2
    if heap[parent] > heap[index]:
        heap[parent], heap[index] = heap[index], heap[parent]
        index = parent
    else:
        break

print(heap)

A [10, 15, 30, 40, 50, 20]

B [15, 10, 30, 40, 50, 20]

C [10, 20, 15, 40, 50, 30]

D [10, 20, 30, 40, 50, 15]

💡 Hint

Remember bubble up swaps the inserted element with its parent if smaller.

The inserted value 15 is appended at the end. It swaps with 30 (its parent) because 15 < 30. No further swaps needed as 15 > 10.

🧠 Conceptual

intermediate

Why does bubble up stop during heap insertion?

In a min-heap insertion, why does the bubble up process stop at some point?

A Because the inserted element is larger than or equal to its parent.

B Because the inserted element reaches the last position in the array.

C Because the heap array is full and cannot grow.

D Because the inserted element becomes the root regardless of value.

💡 Hint

Bubble up swaps only if the child is smaller than the parent.

Bubble up stops when the inserted element is no longer smaller than its parent, maintaining the min-heap property.

❓ Predict Output

advanced

What is the heap after inserting 5 into this max-heap?

Given a max-heap array, what is the heap array after inserting 5 and performing bubble up?

DSA Python

heap = [50, 30, 40, 10, 20]

# Insert 5
heap.append(5)

# Bubble up for max-heap
index = len(heap) - 1
while index > 0:
    parent = (index - 1) // 2
    if heap[parent] < heap[index]:
        heap[parent], heap[index] = heap[index], heap[parent]
        index = parent
    else:
        break

print(heap)

A [50, 30, 40, 10, 20, 5]

B [50, 30, 40, 10, 5, 20]

C [50, 30, 40, 5, 20, 10]

D [5, 50, 40, 10, 20, 30]

💡 Hint

Bubble up swaps only if child is greater than parent in max-heap.

5 is smaller than its parent 40, so no swaps happen. The heap remains the same except 5 is added at the end.

🔧 Debug

advanced

Identify the bug in this bubble up code for min-heap insertion

What is the error in this bubble up code snippet for min-heap insertion?

DSA Python

heap = [10, 20, 30, 40, 50]
heap.append(15)
index = len(heap) - 1
while index > 0:
    parent = index // 2
    if heap[parent] > heap[index]:
        heap[parent], heap[index] = heap[index], heap[parent]
        index = parent
    else:
        break
print(heap)

A The while loop condition should be index >= 0.

B The append operation should be before the while loop.

C The swap should happen only if heap[parent] < heap[index].

D Parent index calculation is wrong; should be (index - 1) // 2.

💡 Hint

Check how parent index is calculated in a binary heap array.

Parent index in a binary heap is (index - 1) // 2, not index // 2. Using index // 2 causes wrong parent selection.

🚀 Application

expert

After inserting 25, what is the heap array?

You have a min-heap: [5, 10, 15, 20, 30, 40]. You insert 25 and perform bubble up. What is the heap array after insertion?

DSA Python

heap = [5, 10, 15, 20, 30, 40]
heap.append(25)
index = len(heap) - 1
while index > 0:
    parent = (index - 1) // 2
    if heap[parent] > heap[index]:
        heap[parent], heap[index] = heap[index], heap[parent]
        index = parent
    else:
        break
print(heap)

A [5, 10, 15, 25, 20, 30, 40]

B [5, 10, 15, 20, 30, 40, 25]

C [5, 10, 15, 20, 25, 40, 30]

D [5, 10, 15, 20, 25, 30, 40]

💡 Hint

Bubble up swaps only if the inserted element is smaller than its parent.

25 is inserted at the end. Its parent is 15 which is smaller, so no swaps happen. Heap remains with 25 at the end.

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