Heap Extract Min or Max Bubble Down in DSA Typescript - 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.

function bubbleDown(heap: number[], index: number = 0): void {
  const length = heap.length;
  let smallest = index;
  const left = 2 * index + 1;
  const right = 2 * index + 2;

  if (left < length && heap[left] < heap[smallest]) smallest = left;
  if (right < length && heap[right] < heap[smallest]) smallest = right;

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

This code removes the top element from a min-heap and moves the last element down to restore heap order by swapping with smaller children.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to bubbleDown that compare and swap elements.
• How many times: At most once per level of the heap, moving down from root to leaf.

How Execution Grows With Input

Each recursive call moves down one level in the heap tree, which grows slowly as the heap size grows.

Input Size (n)	Approx. Operations (levels)
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: The number of steps grows slowly, roughly with the height of the heap, which is much smaller than the total number of elements.

Final Time Complexity

Time Complexity: O(log n)

This means the time to fix the heap grows slowly, proportional to the height of the heap tree.

Common Mistake

[X] Wrong: "Bubble down takes linear time because it might check every element in the heap."

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

Interview Connect

Understanding this helps you explain how heaps efficiently keep order when removing items, a key skill for many coding challenges.

Self-Check

What if we changed the heap to a max-heap? How would the time complexity of bubble down change?