Heap extraction (bubble down) in Data Structures Theory - Time & Space Complexity

Time Complexity: Heap extraction (bubble down)

O(log n)

Understanding Time Complexity

When we remove the top item from a heap, we need to restore its order. This process is called bubble down.

We want to know how the time to do this grows as the heap gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following heap extraction code.

function heapExtract(heap) {
  if (heap.size === 0) return null;
  const top = heap[0];
  heap[0] = heap[heap.size - 1];
  heap.size--;
  bubbleDown(heap, 0);
  return top;
}

function bubbleDown(heap, index) {
  let left = 2 * index + 1;
  let right = 2 * index + 2;
  let smallest = index;
  if (left < heap.size && heap[left] < heap[smallest]) smallest = left;
  if (right < heap.size && 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 restores heap order by moving the new root down.

Identify Repeating Operations

Look at what repeats during bubble down.

• Primary operation: Comparing and swapping the current node with its smaller child.
• How many times: At most once per level of the heap, moving down from root to leaf.

How Execution Grows With Input

Each bubble down step moves one level down the heap tree.

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: The number of steps grows slowly, roughly with the height of the heap, which increases as the logarithm of n.

Final Time Complexity

Time Complexity: O(log n)

This means the time to restore heap order grows slowly as the heap size grows, increasing by about one step each time the heap size doubles.

Common Mistake

[X] Wrong: "Bubble down takes the same time no matter the heap size because it just swaps a few elements."

[OK] Correct: The number of swaps depends on the heap height, which grows with the size of the heap, so bigger heaps can take more steps.

Interview Connect

Understanding how bubble down works and its time cost helps you explain heap operations clearly and shows you know how data structures behave as they grow.

Self-Check

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