Heap Extract Min or Max Bubble Down in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the purpose of the 'bubble down' operation in a heap after extracting the min or max element?

The 'bubble down' operation restores the heap property by moving the new root element down the tree until it is in the correct position, ensuring the heap remains a valid min-heap or max-heap.

beginner

In a min-heap, after extracting the minimum element, which element replaces the root before bubbling down?

The last element in the heap (the rightmost leaf) replaces the root before the bubble down process starts.

intermediate

Describe the condition to swap elements during bubble down in a max-heap.

In a max-heap, during bubble down, swap the current node with its largest child if the child is greater than the current node, to maintain the max-heap property.

beginner

What is the time complexity of the extract min or max operation including bubble down in a heap of size n?

The time complexity is O(log n) because bubble down moves down the height of the heap, which is proportional to log n.

beginner

Why do we replace the root with the last element before bubbling down during extraction?

Replacing the root with the last element keeps the heap complete (no gaps) and allows us to restore the heap property by bubbling down.

What element is removed during the extract min operation in a min-heap?

A The last leaf element

B The root element

C The largest element

D A random element

In a min-heap, the root element is the minimum and is removed during extract min.

After removing the root in a max-heap, which element is moved to the root before bubbling down?

A The left child of the root

B The right child of the root

C The smallest element

D The last element in the heap

The last element in the heap replaces the root to maintain completeness before bubbling down.

During bubble down in a min-heap, when do you swap the current node with a child?

A If the current node is larger than the smallest child

B If the current node is smaller than both children

C If the current node is equal to the largest child

D Always swap with the left child

You swap if the current node is larger than the smallest child to restore the min-heap property.

What is the height of a heap with n elements?

A n squared

B n

C log n

D Square root of n

A heap is a complete binary tree, so its height is proportional to log n.

What is the main goal of the bubble down operation after extraction?

A To restore the heap property

B To remove duplicates

C To increase the heap size

D To sort the heap

Bubble down restores the heap property after the root is replaced.

Explain the steps involved in extracting the minimum element from a min-heap and how bubble down works.

Think about how to keep the heap complete and ordered after removal.

Describe why bubble down is necessary after extracting the max or min element from a heap.

Consider what happens when the root is replaced by the last element.

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