Heap Extract Min or Max Bubble Down in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the heap array after extracting the min element?

Given a min-heap represented as an array, what is the state of the heap array after extracting the minimum element and performing bubble down?

DSA Python

heap = [2, 5, 3, 9, 7, 6]

# Extract min (2) and bubble down
heap[0] = heap[-1]
heap.pop()

# Bubble down process
index = 0
size = len(heap)
while True:
    left = 2 * index + 1
    right = 2 * index + 2
    smallest = index

    if left < size and heap[left] < heap[smallest]:
        smallest = left
    if right < size and heap[right] < heap[smallest]:
        smallest = right
    if smallest == index:
        break
    heap[index], heap[smallest] = heap[smallest], heap[index]
    index = smallest

print(heap)

A [5, 3, 6, 9, 7]

B [3, 5, 6, 9, 7]

C [6, 5, 3, 9, 7]

D [3, 5, 7, 9, 6]

💡 Hint

Remember to replace the root with the last element and then bubble down by swapping with the smaller child.

After removing the root (2), we replace it with the last element (6). Then we bubble down:

• Compare 6 with children 5 and 3; 3 is smallest, swap 6 and 3.
• Now 6 is at index 2, children are 9 and 7, no smaller child, stop.

Final heap: [3, 5, 6, 9, 7]

❓ Predict Output

intermediate

What is the max-heap after extracting the max element and bubbling down?

Given a max-heap array, what is the heap after extracting the maximum element and performing bubble down?

DSA Python

heap = [20, 18, 15, 10, 12, 9, 8]

# Extract max (20) and bubble down
heap[0] = heap[-1]
heap.pop()

index = 0
size = len(heap)
while True:
    left = 2 * index + 1
    right = 2 * index + 2
    largest = index

    if left < size and heap[left] > heap[largest]:
        largest = left
    if right < size and heap[right] > heap[largest]:
        largest = right
    if largest == index:
        break
    heap[index], heap[largest] = heap[largest], heap[index]
    index = largest

print(heap)

A [15, 12, 18, 10, 9, 8]

B [18, 10, 15, 8, 12, 9]

C [18, 12, 15, 9, 10, 8]

D [18, 12, 15, 10, 8, 9]

💡 Hint

Replace root with last element and bubble down by swapping with the larger child.

After removing 20, replace root with 8. Bubble down:

• Compare 8 with children 18 and 15; 18 is largest, swap.
• Now 8 at index 1, children 10 and 12; 12 is largest, swap.
• Now 8 at index 4, no children, stop.

Final heap: [18, 12, 15, 10, 8, 9]

🔧 Debug

advanced

Identify the error in bubble down implementation for min-heap extract

What error will this code produce when extracting min from a min-heap and bubbling down?

DSA Python

heap = [4, 7, 6, 9, 10]
heap[0] = heap.pop()
index = 0
size = len(heap)
while True:
    left = 2 * index + 1
    right = 2 * index + 2
    smallest = index
    if left < size and heap[left] < heap[smallest]:
        smallest = left
    if right < size and heap[right] < heap[smallest]:
        smallest = right
    if smallest == index:
        break
    heap[index], heap[smallest] = heap[smallest], heap[index]
    index = smallest
print(heap)

A IndexError: pop from empty list

B TypeError: 'int' object is not subscriptable

C No error, outputs [6, 7, 10, 9]

D ValueError: list.remove(x): x not in list

💡 Hint

Check how pop() is used and what it returns.

The code executes without any error. heap[0] = heap.pop() pops 10 and assigns it to heap[0], resulting in heap = [10, 7, 6, 9]. Then bubble down:

• At index 0 (10), left=7 <10, right=6 <7, so smallest=2, swap with 6: [6, 7, 10, 9].
• At index 2 (10), no children, stop.

Final output: [6, 7, 10, 9]. No runtime error occurs.

❓ Predict Output

advanced

What is the heap after extracting max and bubbling down with duplicate values?

Given a max-heap with duplicates, what is the heap array after extracting the max and bubbling down?

DSA Python

heap = [30, 20, 20, 15, 10, 10, 5]
heap[0] = heap[-1]
heap.pop()
index = 0
size = len(heap)
while True:
    left = 2 * index + 1
    right = 2 * index + 2
    largest = index
    if left < size and heap[left] > heap[largest]:
        largest = left
    if right < size and heap[right] > heap[largest]:
        largest = right
    if largest == index:
        break
    heap[index], heap[largest] = heap[largest], heap[index]
    index = largest
print(heap)

A [20, 15, 20, 5, 10, 10]

B [20, 15, 10, 20, 10, 5]

C [20, 20, 10, 10, 15, 5]

D [20, 20, 10, 15, 10, 5]

💡 Hint

When children have equal values, bubble down swaps with the left child first if it is larger or equal.

After removing 30, replace root with 5. Bubble down:

• Compare 5 with children 20 and 20; left 20 > 5 so largest=1, right 20 not >20, swap with left 20.
• Now 5 at index 1, children 15 and 10; 15 largest, swap with index 3.
• Now 5 at index 3, no children, stop.

Final heap: [20, 15, 20, 5, 10, 10]

🧠 Conceptual

expert

Why is bubble down necessary after extracting min or max from a heap?

Choose the best explanation for why the bubble down operation is necessary after extracting the root element from a heap.

A Because after replacing the root with the last element, the heap property might be violated and bubble down restores it by moving the element down to its correct position.

B Because bubble down removes duplicate elements from the heap to maintain uniqueness.

C Because bubble down sorts the entire heap array to maintain ascending or descending order.

D Because bubble down swaps the root with the last element to prepare for the next extraction.

💡 Hint

Think about what happens to the heap property after removing the root and replacing it.

When the root is removed, the last element replaces it. This element may be smaller or larger than its children, violating the heap property. Bubble down moves it down the tree by swapping with the smaller (min-heap) or larger (max-heap) child until the heap property is restored.

Practice

1. What is the main purpose of the bubble down operation in a min-heap after extracting the minimum element?

easy

A. To remove the maximum element from the heap

B. To insert a new element at the bottom of the heap

C. To swap the last element with the root without any further changes

D. To restore the min-heap property by moving the root element down to its correct position

Solution

1. Step 1: Understand extract-min operation

   When we remove the minimum element (root) from a min-heap, the last element is moved to the root position.

2. Step 2: Apply bubble down to restore heap

   The bubble down operation moves this element down the tree to restore the min-heap property by swapping it with the smaller child until correct.

3. Final Answer:

   To restore the min-heap property by moving the root element down to its correct position -> Option D

4. Quick Check:

   Bubble down fixes heap after extract-min [OK]

Hint: Bubble down fixes heap after removing root [OK]

Common Mistakes:

• Thinking bubble down inserts new elements
• Confusing bubble down with bubble up
• Assuming bubble down removes max element

2. Which of the following is the correct Python syntax to swap two elements at indices i and j in a list heap during bubble down?

easy

A. swap(heap[i], heap[j])

B. heap[i] = heap[j]; heap[j] = heap[i]

C. heap[i], heap[j] = heap[j], heap[i]

D. heap.swap(i, j)

Solution

1. Step 1: Recall Python tuple unpacking syntax

   Python allows swapping two variables in one line using tuple unpacking: a, b = b, a.

2. Step 2: Apply to list elements

   To swap elements at indices i and j in list heap, use heap[i], heap[j] = heap[j], heap[i].

3. Final Answer:

   heap[i], heap[j] = heap[j], heap[i] -> Option C

4. Quick Check:

   Python swap uses tuple unpacking [OK]

Hint: Use tuple unpacking to swap list elements [OK]

Common Mistakes:

• Assigning one element twice causing same value
• Using non-existent swap function
• Trying method swap on list which doesn't exist

3. Given the min-heap represented as heap = [2, 5, 3, 10, 7], after extracting the minimum element and performing bubble down, what will be the heap array?

medium

A. [3, 5, 7, 10]

B. [3, 7, 5, 10]

C. [5, 3, 7, 10]

D. [5, 7, 3, 10]

Solution

1. Step 1: Extract min and replace root

   Remove 2 (root). Move last element 7 to root: heap becomes [7, 5, 3, 10].

2. Step 2: Bubble down to restore min-heap

   Compare 7 with children 5 and 3. Smallest child is 3 at index 2. Swap 7 and 3: heap becomes [3, 5, 7, 10].

3. Final Answer:

   [3, 5, 7, 10] -> Option A

4. Quick Check:

   After extract-min and bubble down heap = [3, 5, 7, 10] [OK]

Hint: Replace root with last, then swap down with smaller child [OK]

Common Mistakes:

• Not swapping with the smallest child
• Forgetting to remove the extracted element
• Swapping with the wrong child

4. Consider this bubble down code snippet for a max-heap extract operation:

def bubble_down(heap, index):
    left = 2 * index + 1
    right = 2 * index + 2
    largest = index
    if left < len(heap) and heap[left] > heap[largest]:
        largest = left
    if right < len(heap) and heap[right] > heap[largest]:
        largest = right
    if largest != index:
        heap[index], heap[largest] = heap[largest], heap[index]
        bubble_down(heap, largest)

What is the bug if the heap is empty when this function is called?

medium

A. IndexError because index 0 is accessed in empty list

B. No bug, function handles empty heap correctly

C. Infinite recursion due to missing base case

D. TypeError because heap is not a list

Solution

1. Step 1: Trace execution on empty heap

   For heap=[], index=0, len(heap)=0. left=1 < 0 is False, right=2 < 0 is False. largest remains 0. Due to short-circuit, no heap access.

2. Step 2: No swap or recursion triggered

   largest == index, so no swap executed and no recursive call. Function exits safely.

3. Final Answer:

   No bug, function handles empty heap correctly -> Option B

4. Quick Check:

   Short-circuit 'and' prevents invalid access [OK]

Hint: Python 'and' short-circuits, safely handles empty heap [OK]

Common Mistakes:

• Thinking heap[index] accessed causing IndexError
• Expecting infinite recursion
• Confusing IndexError with TypeError

5. You have a max-heap represented as [20, 18, 15, 10, 12, 9, 8]. After extracting the maximum element and performing bubble down, what is the resulting heap array?

hard

A. [18, 12, 15, 10, 8, 9]

B. [18, 12, 15, 10, 9, 8]

C. [18, 15, 12, 10, 9, 8]

D. [18, 10, 15, 8, 12, 9]

Solution

1. Step 1: Extract max and replace root

   Remove 20 (root). Move last element 8 to root: heap becomes [8, 18, 15, 10, 12, 9].

2. Step 2: Bubble down to restore max-heap

   Compare 8 with children 18 and 15. Largest child is 18 at index 1. Swap 8 and 18: [18, 8, 15, 10, 12, 9].

3. Step 3: Continue bubble down

   Now at index 1, compare 8 with children 10 and 12. Largest child is 12 at index 4. Swap 8 and 12: [18, 12, 15, 10, 8, 9].

4. Step 4: Check next level

   Index 4 has no children, stop bubbling down.

5. Final Answer:

   [18, 12, 15, 10, 8, 9] -> Option A

6. Quick Check:

   Extract max + bubble down = [18, 12, 15, 10, 8, 9] [OK]

Hint: Swap with largest child until no bigger child exists [OK]

Common Mistakes:

• Swapping with smaller child
• Stopping bubble down too early
• Forgetting to remove last element