Heap Extract Min or Max Bubble Down in DSA Python

Mental Model

When we remove the top value from a heap, we replace it with the last value and then push it down to restore the heap order.

Analogy: Imagine a pyramid of blocks where the top block is removed. To keep the pyramid stable, you take the bottom block and move it down step by step to the right place.

      [10]
     /    \
  [15]    [20]
  /  \    /  \
[30][40][50][60]

Top is 10 (min or max), children below maintain order.

Dry Run Walkthrough

Input: min-heap: [10, 15, 20, 30, 40, 50, 60], extract min

Goal: Remove the smallest value (10) and restore min-heap order by pushing down the replacement

Step 1: Remove root 10, replace with last element 60

Heap array: [60, 15, 20, 30, 40, 50]

Why: We remove the top and fill the gap with the last element to keep complete tree shape

Step 2: Compare 60 with children 15 and 20; swap with smaller child 15

Heap array: [15, 60, 20, 30, 40, 50]

Why: 60 is bigger than 15, so swap to restore min-heap property

Step 3: Compare 60 with children 30 and 40; swap with smaller child 30

Heap array: [15, 30, 20, 60, 40, 50]

Why: 60 is bigger than 30, so swap again to maintain heap order

Step 4: 60 has no children smaller than itself, stop bubbling down

Heap array: [15, 30, 20, 60, 40, 50]

Why: Heap property restored, no further swaps needed

Result:

Heap array after extract min and bubble down: [15, 30, 20, 60, 40, 50]

Annotated Code

DSA Python

class MinHeap:
    def __init__(self, data=None):
        self.heap = data if data else []

    def left(self, i):
        return 2 * i + 1

    def right(self, i):
        return 2 * i + 2

    def bubble_down(self, i):
        size = len(self.heap)
        while True:
            left = self.left(i)
            right = self.right(i)
            smallest = i

            if left < size and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < size and self.heap[right] < self.heap[smallest]:
                smallest = right

            if smallest == i:
                break

            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            i = smallest

    def extract_min(self):
        if not self.heap:
            return None
        min_val = self.heap[0]
        last_val = self.heap.pop()
        if self.heap:
            self.heap[0] = last_val
            self.bubble_down(0)
        return min_val


# Driver code
heap = MinHeap([10, 15, 20, 30, 40, 50, 60])
print("Initial heap:", heap.heap)
min_val = heap.extract_min()
print("Extracted min:", min_val)
print("Heap after extract min and bubble down:", heap.heap)

if not self.heap: return None

handle empty heap edge case

min_val = self.heap[0]

store root value to return

last_val = self.heap.pop()

remove last element to replace root

if self.heap: self.heap[0] = last_val self.bubble_down(0)

replace root and restore heap order by bubbling down

while True: left = self.left(i) right = self.right(i) smallest = i if left < size and self.heap[left] < self.heap[smallest]: smallest = left if right < size and self.heap[right] < self.heap[smallest]: smallest = right if smallest == i: break self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i] i = smallest

bubble down by swapping with smaller child until heap property restored

Output

Initial heap: [10, 15, 20, 30, 40, 50, 60]

Extracted min: 10

Heap after extract min and bubble down: [15, 30, 20, 60, 40, 50]

Complexity Analysis

Time: O(log n) because bubble down moves down the height of the heap which is log n

Space: O(1) because all operations are done in place without extra space

vs Alternative: Compared to rebuilding the heap from scratch (O(n)), bubble down after extract is more efficient at O(log n)

Edge Cases

empty heap

extract_min returns None without error

DSA Python

if not self.heap:
    return None

heap with one element

extract_min removes and returns the only element, heap becomes empty

DSA Python

last_val = self.heap.pop()
if self.heap:
    self.heap[0] = last_val

heap where bubble down is not needed

after replacing root, no swaps occur because heap property holds

DSA Python

if smallest == i:
    break

When to Use This Pattern

When you see a problem asking to remove the top element from a heap and maintain heap order, use bubble down to restore the heap efficiently.

Common Mistakes

Mistake: Not replacing the root with the last element before bubbling down
Fix: Always replace the root with the last element before starting bubble down

Mistake: Swapping with the wrong child (not the smaller for min-heap)
Fix: Compare both children and swap with the smallest child to maintain min-heap property

Mistake: Not handling empty heap before extraction
Fix: Check if heap is empty and return None or handle gracefully

Summary

Removes the top element from a heap and restores heap order by pushing down the replacement.

Use when extracting min or max from a heap to maintain its structure efficiently.

The key is to replace the root with the last element and bubble it down by swapping with the smaller (or larger) child until order 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