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

Time Complexity: Heap Extract Min or Max Bubble Down

O(log n)

Understanding Time Complexity

We analyze how long it takes to remove the top element from a heap and restore order.

How does the work grow as the heap size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func bubbleDown(heap []int, index int) {
    n := len(heap)
    smallest := index
    left := 2*index + 1
    right := 2*index + 2

    if left < n && heap[left] < heap[smallest] {
        smallest = left
    }
    if right < n && heap[right] < heap[smallest] {
        smallest = right
    }
    if smallest != index {
        heap[index], heap[smallest] = heap[smallest], heap[index]
        bubbleDown(heap, smallest)
    }
}

This code restores the heap property by moving the root element down to its correct position.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls moving down the heap levels.
• How many times: Up to the height of the heap, which is about log n.

How Execution Grows With Input

Each recursive step compares and swaps with children, moving down one level.

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

Pattern observation: Operations grow slowly, roughly proportional to the height of the heap, which increases logarithmically.

Final Time Complexity

Time Complexity: O(log n)

This means the time to fix the heap grows slowly as the heap gets bigger, only about the height of the tree.

Common Mistake

[X] Wrong: "Bubble down takes linear time because it looks at many elements."

[OK] Correct: It only moves down one path from root to leaf, not all elements, so it takes time proportional to the tree height, not the total number of elements.

Interview Connect

Understanding this helps you explain how heaps keep their order efficiently after removals, a key skill for many coding problems.

Self-Check

"What if the heap was a ternary heap (each node has 3 children) instead of binary? How would the time complexity change?"