Heap Extract Min or Max Bubble Down in DSA Python - Build from Scratch

Heap Extract Min or Max Bubble Down

📖 Scenario: Imagine you are managing a priority queue for tasks where the highest priority task should be done first. You use a heap data structure to keep tasks ordered by priority.

🎯 Goal: You will build a simple max-heap and implement the extract max operation. This operation removes the highest priority task (the root) and then fixes the heap by moving the new root down to keep the heap property intact. This process is called bubble down.

📋 What You'll Learn

Create a list called heap representing a max-heap with exact values

Create a variable heap_size to track the number of elements in the heap

Write a function bubble_down(index) that moves the element at index down to restore max-heap order

Write a function extract_max() that removes and returns the max element, then calls bubble_down(0)

Print the heap list after extracting the max element

💡 Why This Matters

🌍 Real World

Heaps are used in task scheduling, priority queues, and algorithms like heapsort.

💼 Career

Understanding heap operations is important for software engineering roles involving efficient data processing and algorithm design.

1

Create the initial max-heap list

Create a list called heap with these exact values: [90, 70, 80, 50, 60, 40, 30]. Also create a variable heap_size and set it to the length of heap.

DSA Python

# Create the heap list and heap_size variable
# Your code here

Hint

The heap is a list with the largest number at the front. Use len() to get the size.

2

Define the bubble_down function

Define a function called bubble_down(index) that moves the element at index down the heap to restore max-heap order. Use heap and heap_size inside the function. Use variables left = 2 * index + 1 and right = 2 * index + 2 to find children. Swap with the largest child if needed and continue until no swaps are needed.

DSA Python

heap = [90, 70, 80, 50, 60, 40, 30]
heap_size = len(heap)

def bubble_down(index):
    # Your code here

Hint

Use a loop to keep swapping the element with the larger child until it is larger than both children or no children exist.

3

Define the extract_max function

Define a function called extract_max() that removes and returns the max element from heap. Replace the root with the last element, reduce heap_size by 1, then call bubble_down(0) to fix the heap.

DSA Python

heap = [90, 70, 80, 50, 60, 40, 30]
heap_size = len(heap)

def bubble_down(index):
    largest = index
    while True:
        left = 2 * index + 1
        right = 2 * index + 2
        if left  heap[largest]:
            largest = left
        if right  heap[largest]:
            largest = right
        if largest != index:
            heap[index], heap[largest] = heap[largest], heap[index]
            index = largest
        else:
            break

def extract_max():
    # Your code here

Hint

Remember to update heap_size and call bubble_down(0) after replacing the root.

4

Extract max and print the heap

Call the function extract_max() and then print the current state of the heap list sliced up to heap_size to show the heap after extraction.

DSA Python

heap = [90, 70, 80, 50, 60, 40, 30]
heap_size = len(heap)

def bubble_down(index):
    largest = index
    while True:
        left = 2 * index + 1
        right = 2 * index + 2
        if left  heap[largest]:
            largest = left
        if right  heap[largest]:
            largest = right
        if largest != index:
            heap[index], heap[largest] = heap[largest], heap[index]
            index = largest
        else:
            break

def extract_max():
    global heap_size
    if heap_size == 0:
        return None
    max_value = heap[0]
    heap[0] = heap[heap_size - 1]
    heap_size -= 1
    bubble_down(0)
    return max_value

extract_max()
# Print the heap list sliced up to heap_size
# Your code here

Hint

After extracting max, print the heap list sliced to heap_size to see the updated heap.

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