Heap Extract Min or Max Bubble Down in DSA C++ - Time & Space Complexity

Time Complexity: Heap Extract Min or Max Bubble Down

O(log n)

Understanding Time Complexity

We want to understand how long it takes to remove the smallest or largest item from a heap and fix the heap order.

How does the time needed grow as the heap gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Extract min from a min-heap and bubble down to fix heap
int extractMin(std::vector<int>& heap) {
    int minVal = heap[0];
    heap[0] = heap.back();
    heap.pop_back();
    int i = 0;
    int n = heap.size();
    while (true) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int smallest = i;
        if (left < n && heap[left] < heap[smallest]) smallest = left;
        if (right < n && heap[right] < heap[smallest]) smallest = right;
        if (smallest == i) break;
        std::swap(heap[i], heap[smallest]);
        i = smallest;
    }
    return minVal;
}
    

This code removes the smallest item from a min-heap and then moves the new root down to restore the heap order.

Identify Repeating Operations

• Primary operation: The while loop that moves the root element down the heap to fix order.
• How many times: At most, this loop runs once per level of the heap, from root to leaf.

How Execution Grows With Input

Each time we bubble down, we move one level down the heap tree. The heap height grows slowly as the heap size grows.

Input Size (n)	Approx. Operations (levels to bubble down)
10	About 3 to 4 steps
100	About 6 to 7 steps
1000	About 9 to 10 steps

Pattern observation: The number of steps grows slowly, roughly proportional to the height of the heap, which is about log base 2 of n.

Final Time Complexity

Time Complexity: O(log n)

This means the time to extract and fix the heap grows slowly, increasing only a little even if the heap gets much bigger.

Common Mistake

[X] Wrong: "Extracting min takes constant time because we just remove the root."

[OK] Correct: Removing the root is quick, but fixing the heap order by moving the new root down can take several steps depending on heap height.

Interview Connect

Knowing this time complexity helps you explain why heaps are efficient for priority queues and sorting, showing you understand how data structure operations scale.

Self-Check

"What if the heap was a max-heap instead of a min-heap? How would the time complexity of extract and bubble down change?"