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.