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?"

Practice

1. What is the main purpose of the bubble down operation in a min-heap after extracting the minimum element?

easy

A. To remove the largest element from the heap

B. To insert a new element at the bottom of the heap

C. To restore the heap property by moving the root element down to its correct position

D. To swap the last element with the root without any further changes

Solution

1. Step 1: Understand extract-min in a min-heap

   Extracting the minimum removes the root, which breaks the heap property.

2. Step 2: Role of bubble down

   Bubble down moves the new root element down to restore the min-heap property by swapping with smaller children.

3. Final Answer:

   To restore the heap property by moving the root element down to its correct position -> Option C

4. Quick Check:

   Bubble down fixes heap after extract-min [OK]

Hint: Bubble down fixes heap by pushing root down after extract [OK]

Common Mistakes:

• Thinking bubble down inserts new elements
• Confusing bubble down with bubble up
• Assuming bubble down removes largest element

2. Which of the following is the correct syntax to swap two elements arr[i] and arr[j] in JavaScript during bubble down?

easy

A. [arr[i], arr[j]] = [arr[j], arr[i]];

B. swap(arr[i], arr[j]);

C. arr[i] = arr[j]; arr[j] = arr[i];

D. temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

Solution

1. Step 1: Identify JavaScript swap syntax

   ES6 allows swapping with destructuring: [a, b] = [b, a].

2. Step 2: Check each option

   [arr[i], arr[j]] = [arr[j], arr[i]]; uses correct destructuring syntax. temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; is valid but missing var or let for temp, so incomplete. Options A and C are incorrect syntax or logic.

3. Final Answer:

   [arr[i], arr[j]] = [arr[j], arr[i]]; -> Option A

4. Quick Check:

   Use destructuring swap in JS [OK]

Hint: Use ES6 destructuring for swap: [a,b]=[b,a] [OK]

Common Mistakes:

• Using undefined swap function
• Overwriting values without temp variable
• Incorrect assignment order causing same values

3. Given the min-heap array [2, 5, 3, 8, 10], after extracting the minimum and performing bubble down, what is the resulting heap array?

medium

A. [3, 5, 8, 10]

B. [5, 3, 8, 10]

C. [5, 8, 3, 10]

D. [3, 5, 10, 8]

Solution

1. Step 1: Extract min and replace root

   Remove 2 (root), move last element 10 to root: [10, 5, 3, 8]

2. Step 2: Bubble down 10

   Compare 10 with children 5 and 3. Smallest child is 3 at index 2. Swap 10 and 3: [3, 5, 10, 8]. Now 10 at index 2 has no children (indices 5 and 6 out of bounds), so stop.

3. Final Answer:

   [3, 5, 10, 8] -> Option D

4. Quick Check:

   Bubble down restores min-heap [OK]

Hint: Replace root with last, then swap down with smaller child [OK]

Common Mistakes:

• Not swapping with smallest child
• Forgetting to remove last element
• Swapping with larger child

4. Consider this bubble down code snippet for a max-heap extract operation:

function bubbleDown(arr, index) {
  let left = 2 * index + 1;
  let right = 2 * index + 2;
  let largest = index;
  if (left < arr.length && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < arr.length && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest !== index) {
    [arr[index], arr[largest]] = [arr[largest], arr[index]];
    bubbleDown(arr, largest);
  }
}

What is the bug if the heap array is empty after extract and bubbleDown is called with index 0?

medium

A. Infinite recursion because largest never equals index

B. No bug; function handles empty array correctly

C. Accessing arr[0] causes undefined behavior on empty array

D. Swapping elements without checking array length

Solution

1. Step 1: Analyze empty array case

   If arr is empty, arr.length = 0, left and right indices are 1 and 2, both >= length, so no swaps.

2. Step 2: Check access at arr[index]

   No accesses occur because child indices out of bounds and && short-circuits prevent evaluating arr[largest]. Function handles empty array safely.

3. Final Answer:

   No bug; function handles empty array correctly -> Option B

4. Quick Check:

   Check array length before accessing index [OK]

Hint: Always check array length before accessing indices [OK]

Common Mistakes:

• Assuming recursion stops automatically
• Ignoring empty array edge case
• Not validating index bounds

5. You have a max-heap represented as [50, 30, 40, 10, 20, 35]. After extracting the maximum and performing bubble down, what is the final heap array?

hard

A. [40, 30, 35, 10, 20]

B. [40, 30, 35, 20, 10]

C. [40, 35, 30, 10, 20]

D. [35, 30, 40, 10, 20]

Solution

1. Step 1: Extract max and replace root

   Remove 50 (root), move last element 35 to root: [35, 30, 40, 10, 20]

2. Step 2: Bubble down 35

   Compare 35 with children 30 and 40. Largest child is 40 at index 2. Swap 35 and 40: [40, 30, 35, 10, 20]. Now 35 at index 2 has children beyond array length, so stop.

3. Final Answer:

   [40, 30, 35, 10, 20] -> Option A

4. Quick Check:

   Bubble down swaps with largest child in max-heap [OK]

Hint: Swap root with largest child until heap property restored [OK]

Common Mistakes:

• Swapping with smaller child
• Not moving last element to root
• Stopping bubble down too early