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.