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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Extract-Min on a Min-Heap

What is the state of the min-heap array after extracting the minimum element once?

DSA C++

std::vector<int> heap = {1, 3, 6, 5, 9, 8};
// Extract min operation (remove root and bubble down)
// After extraction, heap becomes:
// 1. Replace root with last element
// 2. Remove last element
// 3. Bubble down the new root

// Resulting heap array:

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

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

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

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

💡 Hint

Remember to replace the root with the last element and then bubble down to restore heap property.

After removing the root (1), replace it with last element (8). Then bubble down 8: compare with children 3 and 6, swap with smaller child 3. Now 8 is at index 1, compare with children 5 and 9, swap with smaller child 5. Final heap: [3, 5, 6, 8, 9].

❓ Predict Output

intermediate

Output of Extract-Max on a Max-Heap

What is the state of the max-heap array after extracting the maximum element once?

DSA C++

std::vector<int> heap = {20, 18, 15, 13, 10, 8, 9};
// Extract max operation (remove root and bubble down)
// After extraction, heap becomes:
// 1. Replace root with last element
// 2. Remove last element
// 3. Bubble down the new root

// Resulting heap array:

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

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

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

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

💡 Hint

After replacing root with last element, bubble down by swapping with the larger child.

Remove root (20), replace with last element (9). Bubble down 9: children are 18 and 15, swap with larger child 18. Now at index 1, children 13 and 10, swap with larger child 13. Final heap: [18, 13, 15, 9, 10, 8].

🧠 Conceptual

advanced

Why Bubble Down is Necessary After Extracting Root in a Heap

Why do we need to perform the bubble down operation after extracting the root element from a heap?

A Because the last element moved to the root may violate the heap property and needs to be moved down to restore it.

B Because the heap size increases and we need to rebalance the tree by moving elements down.

C Because bubble down removes duplicate elements from the heap after extraction.

D Because bubble down sorts the entire heap array after extraction.

💡 Hint

Think about what happens when the last element replaces the root.

After removing the root, the last element is placed at the root. This element may be larger (in min-heap) or smaller (in max-heap) than its children, violating the heap property. Bubble down moves it down to restore the heap order.

🔧 Debug

advanced

Identify the Bug in Bubble Down Implementation

What is the bug in this bubble down code snippet for a min-heap?

DSA C++

void bubbleDown(std::vector<int>& heap, int index) {
  int left = 2 * index + 1;
  int right = 2 * index + 2;
  int smallest = index;
  if (left < heap.size() && heap[left] < heap[smallest]) {
    smallest = left;
  }
  if (right < heap.size() && heap[right] < heap[smallest]) {
    smallest = right;
  }
  if (smallest != index) {
    std::swap(heap[index], heap[smallest]);
    bubbleDown(heap, smallest);
  }
}

A The function swaps elements before checking if smallest is different from index.

B The function does not check if index is within bounds before accessing children.

C The function should use a loop instead of recursion to avoid stack overflow.

D No bug; the code correctly bubbles down the element.

💡 Hint

Check the conditions and recursive call carefully.

The code correctly finds the smallest child and swaps if needed, then recursively bubbles down. It checks bounds before accessing children. The recursion is valid for typical heap sizes.

🚀 Application

expert

Number of Items After Multiple Extract-Min Operations

Given a min-heap with 10 elements, how many elements remain after performing 3 extract-min operations?

A 6

B 7

C 3

D 10

💡 Hint

Each extract-min removes exactly one element from the heap.

Each extract-min removes the root element, reducing the heap size by one. After 3 extractions, 10 - 3 = 7 elements remain.

Practice

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

easy

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

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 remove the maximum element from the heap

Solution

1. Step 1: Understand extract-min operation

   When the minimum element (root) is removed, 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 with the smaller child.

3. Final Answer:

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

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 C++ syntax to swap two elements heap[i] and heap[j] during bubble down?

easy

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

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

C. swap(heap[i], heap[j]) = true;

D. swap(heap[i], heap[j]);

Solution

1. Step 1: Recall C++ swap function usage

   The standard way to swap two variables in C++ is using swap(a, b); from <algorithm>.

2. Step 2: Check each option

   swap(heap[i], heap[j]); uses correct syntax. heap[i] = heap[j]; heap[j] = heap[i]; wrongly assigns values without temporary storage. Options C and D have invalid syntax.

3. Final Answer:

   swap(heap[i], heap[j]); -> Option D

4. Quick Check:

   Correct swap syntax = swap(heap[i], heap[j]); [OK]

Hint: Use standard swap function with two variables [OK]

Common Mistakes:

• Assigning without temporary variable causes errors
• Adding extra symbols after swap call
• Using braces {} after swap incorrectly

3. Given the min-heap array [2, 5, 3, 10, 7], after extracting the minimum element and performing bubble down, what is the resulting heap array?

medium

A. [3, 5, 7, 10]

B. [3, 7, 5, 10]

C. [5, 7, 3, 10]

D. [5, 3, 7, 10]

Solution

1. Step 1: Remove minimum and replace root

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

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

   Compare 7 with children 5 and 3. Smallest child is 3. Swap 7 and 3: [3, 5, 7, 10]. Now 7 has children 10 only, no swap needed.

3. Final Answer:

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

4. Quick Check:

   Bubble down swaps root with smallest child [OK]

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

Common Mistakes:

• Not swapping with smallest child first
• Forgetting to replace root with last element
• Swapping with larger child by mistake

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

void bubbleDown(vector<int>& heap, int i) {
  int left = 2*i + 1;
  int right = 2*i + 2;
  int largest = i;
  if (left < heap.size() && heap[left] > heap[largest])
    largest = left;
  if (right < heap.size() && heap[right] > heap[largest])
    largest = right;
  if (largest != i) {
    swap(heap[i], heap[largest]);
    bubbleDown(heap, largest);
  }
}

What is the bug if the heap size is 1 and bubbleDown(heap, 0) is called?

medium

A. Infinite recursion because largest never changes

B. No bug; function handles size 1 correctly

C. Accessing left child index 1 causes out-of-range error

D. Swap called even when largest equals i

Solution

1. Step 1: Check conditions for size 1 heap

   For size 1, left = 1 and right = 2, both >= heap.size(), so conditions fail and largest stays i.

2. Step 2: Confirm no recursion or swap

   Since largest == i, no swap or recursive call happens. Function returns safely.

3. Final Answer:

   No bug; function handles size 1 correctly -> Option B

4. Quick Check:

   Bounds checked before access prevents errors [OK]

Hint: Check index bounds before accessing children [OK]

Common Mistakes:

• Assuming out-of-range access without checking
• Thinking recursion always happens
• Swapping when largest equals current index

5. You have a max-heap represented as [50, 30, 40, 10, 20, 35]. After extracting the maximum element and performing bubble down, what is the final heap array?

hard

A. [40, 35, 30, 10, 20]

B. [40, 30, 20, 10, 35]

C. [40, 30, 35, 10, 20]

D. [35, 30, 40, 10, 20]

Solution

1. Step 1: Remove max and replace root

   Remove 50 (root). Move last element 35 to root: [35, 30, 40, 10, 20]

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

   Compare 35 with children 30 and 40. Largest child is 40. Swap 35 and 40: [40, 30, 35, 10, 20]. Now 35 has children 10 and 20, both smaller, so stop.

3. Final Answer:

   [40, 30, 35, 10, 20] -> Option C

4. Quick Check:

   Bubble down swaps with largest child in max-heap [OK]

Hint: Swap root with largest child until heap property restored [OK]

Common Mistakes:

• Swapping with smaller child instead of largest
• Not replacing root with last element before bubble down
• Stopping bubble down too early