Heap Extract Min or Max Bubble Down in DSA Javascript - 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, index = 0) {
  const length = heap.length;
  const element = heap[index];
  while (true) {
    let leftChildIdx = 2 * index + 1;
    let rightChildIdx = 2 * index + 2;
    let swapIdx = null;

    if (leftChildIdx < length && heap[leftChildIdx] < element) {
      swapIdx = leftChildIdx;
    }
    if (rightChildIdx < length && heap[rightChildIdx] < (swapIdx === null ? element : heap[leftChildIdx])) {
      swapIdx = rightChildIdx;
    }
    if (swapIdx === null) break;

    heap[index] = heap[swapIdx];
    heap[swapIdx] = element;
    index = swapIdx;
  }
}

This code moves the root element down the heap to restore the heap property after removing the top item.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that compares and swaps the element with its children to move it down.
• How many times: At most, it runs once per level of the heap, moving down from the root to a leaf.

How Execution Grows With Input

Each step moves the element down one level in the heap tree. The heap height grows slowly as the heap gets bigger.

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 items.

Final Time Complexity

Time Complexity: O(log n)

This means the time to fix the heap grows slowly, only as the height of the heap tree, even if the heap has many items.

Common Mistake

[X] Wrong: "The bubble down takes time proportional to the number of items in the heap (O(n))."

[OK] Correct: The bubble down only moves down the height of the heap tree, which grows much slower than the total number of items.

Interview Connect

Understanding this helps you explain how heaps keep operations efficient, which is a key skill for many coding problems and interviews.

Self-Check

"What if the heap was a complete ternary tree (3 children per node) instead of binary? How would the time complexity of bubble down change?"