Heap Extract Min or Max Bubble Down in DSA C++

Mental Model

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

Analogy: Imagine a pyramid of blocks where the top block is removed. You take the bottom block and place it on top, then slide it down to its correct spot so the pyramid stays stable.

      [1]
     /   \
   [3]   [5]
   / \   / \
 [7] [9][8][10]

Heap array: [1,3,5,7,9,8,10]
↑ top element to extract

Dry Run Walkthrough

Input: Heap array: [1, 3, 5, 7, 9, 8, 10], extract min (top element 1)

Goal: Remove the smallest element (1) and restore the min-heap property by pushing down the last element

Step 1: Remove top element 1, replace it with last element 10

[10, 3, 5, 7, 9, 8]  (size reduced by 1)

Why: We remove the root and put the last element at the root to maintain complete tree shape

Step 2: Compare 10 with children 3 and 5; swap with smallest child 3

[3, 10, 5, 7, 9, 8]

Why: 10 is bigger than 3, so swap to restore min-heap order

Step 3: Compare 10 with children 7 and 9; swap with smallest child 7

[3, 7, 5, 10, 9, 8]

Why: 10 is bigger than 7, so swap to continue restoring order

Step 4: Compare 10 with children (none, since 10 is now a leaf), stop

[3, 7, 5, 10, 9, 8]

Why: No children to compare, heap property restored

Result:

[3, 7, 5, 10, 9, 8]  Extracted min: 1

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

class MinHeap {
public:
    vector<int> heap;

    MinHeap(const vector<int>& elements) {
        heap = elements;
        buildHeap();
    }

    void buildHeap() {
        for (int i = (heap.size() / 2) - 1; i >= 0; i--) {
            bubbleDown(i);
        }
    }

    int extractMin() {
        if (heap.empty()) return -1; // empty heap
        int minVal = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) {
            bubbleDown(0);
        }
        return minVal;
    }

    void bubbleDown(int index) {
        int size = heap.size();
        int smallest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;

        if (left < size && heap[left] < heap[smallest]) {
            smallest = left;
        }
        if (right < size && heap[right] < heap[smallest]) {
            smallest = right;
        }

        if (smallest != index) {
            swap(heap[index], heap[smallest]);
            bubbleDown(smallest); // recursive push down
        }
    }

    void printHeap() {
        for (int val : heap) {
            cout << val << " ";
        }
        cout << endl;
    }
};

int main() {
    vector<int> elements = {1, 3, 5, 7, 9, 8, 10};
    MinHeap h(elements);
    cout << "Initial heap: ";
    h.printHeap();

    int minVal = h.extractMin();
    cout << "Extracted min: " << minVal << endl;
    cout << "Heap after extractMin: ";
    h.printHeap();

    return 0;
}

heap[0] = heap.back(); heap.pop_back();

Replace root with last element and remove last element to keep complete tree

if (!heap.empty()) { bubbleDown(0); }

Restore heap order by pushing down the new root

if (left < size && heap[left] < heap[smallest]) { smallest = left; }

Find smaller child to swap with

if (right < size && heap[right] < heap[smallest]) { smallest = right; }

Check right child for smaller value

if (smallest != index) { swap(heap[index], heap[smallest]); bubbleDown(smallest); }

Swap with smaller child and continue pushing down

Output

Initial heap: 1 3 5 7 9 8 10 

Extracted min: 1

Heap after extractMin: 3 7 5 10 9 8 

Complexity Analysis

Time: O(log n) because bubbleDown moves down the tree height which is log n

Space: O(n) for storing the heap elements in an array

vs Alternative: Compared to rebuilding the heap from scratch (O(n)), extractMin with bubbleDown is faster for single removals

Edge Cases

Empty heap

extractMin returns -1 indicating no element to remove

DSA C++

if (heap.empty()) return -1; // empty heap

Heap with one element

extractMin removes the only element and heap becomes empty

DSA C++

heap[0] = heap.back(); heap.pop_back();

Heap where last element is smaller than children

bubbleDown does not swap and stops immediately

DSA C++

if (smallest != index) { ... } else stop

When to Use This Pattern

When you need to remove the top element from a heap and restore order, use extract with bubbleDown to efficiently fix the heap.

Common Mistakes

Mistake: Not swapping with the smallest child during bubbleDown in a min-heap
Fix: Always compare both children and swap with the smallest to maintain heap property

Mistake: Forgetting to check if children indices are within heap size
Fix: Check left and right child indices against heap size before accessing

Summary

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

Use when you want to extract the min or max element from a heap efficiently.

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