Heap Extract Min or Max Bubble Down in DSA Javascript

Mental Model

When we remove the top value from a heap, we replace it with the last item and then push it down to restore the heap order.

Analogy: Imagine a pyramid of blocks where the top block is removed. To keep the pyramid stable, you move the bottom block to the top and then slide it down to the right place.

       [10]
      /    \
   [15]    [20]
   /  \    /  \
 [30][40][50][60]

Top is 10 (min or max), children below maintain heap order.

Dry Run Walkthrough

Input: Heap array: [10, 15, 20, 30, 40, 50, 60], extract min (remove 10)

Goal: Remove the root (10), replace it with last element (60), then bubble down to restore min-heap order

Step 1: Remove root 10, replace with last element 60

[60, 15, 20, 30, 40, 50]

Why: We remove the top and fill the hole with the last element to keep the tree complete

Step 2: Compare 60 with children 15 and 20; swap with smaller child 15

[15, 60, 20, 30, 40, 50]

Why: To restore min-heap, bubble down 60 by swapping with smaller child

Step 3: Compare 60 with children 30 and 40; swap with smaller child 30

[15, 30, 20, 60, 40, 50]

Why: Continue bubbling down 60 to correct position

Step 4: 60 has no children smaller than itself, stop bubbling down

[15, 30, 20, 60, 40, 50]

Why: Heap order restored, no further swaps needed

Result:

[15, 30, 20, 60, 40, 50]

Annotated Code

DSA Javascript

class MinHeap {
  constructor() {
    this.heap = [];
  }

  extractMin() {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop();

    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return min;
  }

  bubbleDown(index) {
    const length = this.heap.length;
    const element = this.heap[index];

    while (true) {
      let leftChildIdx = 2 * index + 1;
      let rightChildIdx = 2 * index + 2;
      let swapIdx = null;

      if (leftChildIdx < length && this.heap[leftChildIdx] < element) {
        swapIdx = leftChildIdx;
      }

      if (rightChildIdx < length) {
        if ((swapIdx === null && this.heap[rightChildIdx] < element) ||
            (swapIdx !== null && this.heap[rightChildIdx] < this.heap[swapIdx])) {
          swapIdx = rightChildIdx;
        }
      }

      if (swapIdx === null) break;

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

// Driver code
const heap = new MinHeap();
heap.heap = [10, 15, 20, 30, 40, 50, 60];
const extracted = heap.extractMin();
console.log("Extracted min:", extracted);
console.log("Heap after extractMin:", heap.heap.join(", "));

const min = this.heap[0];

store root value to return later

this.heap[0] = this.heap.pop();

replace root with last element to maintain complete tree

this.bubbleDown(0);

restore heap order by pushing new root down

while (true) { ... }

loop to keep bubbling down until heap order is restored

if (leftChildIdx < length && this.heap[leftChildIdx] < element) { swapIdx = leftChildIdx; }

check if left child is smaller and needs swapping

if ((swapIdx === null && this.heap[rightChildIdx] < element) || (swapIdx !== null && this.heap[rightChildIdx] < this.heap[swapIdx])) { swapIdx = rightChildIdx; }

check if right child is smaller than element or left child

if (swapIdx === null) break;

stop if no children are smaller

swap elements and update index to continue bubbling down

perform swap and move down the heap

Output

Extracted min: 10

Heap after extractMin: 15, 30, 20, 60, 40, 50

Complexity Analysis

Time: O(log n) because bubbling down moves down the height of the heap which is log n

Space: O(1) because all operations are done in place without extra storage

vs Alternative: Compared to rebuilding the heap from scratch (O(n)), bubbling down after extract is more efficient (O(log n))

Edge Cases

Empty heap

extractMin returns null immediately

DSA Javascript

if (this.heap.length === 0) return null;

Heap with one element

extractMin returns the single element and heap becomes empty

DSA Javascript

if (this.heap.length === 1) return this.heap.pop();

Heap where last element is larger than root

bubbleDown swaps root with smaller children correctly

DSA Javascript

while (true) { ... } loop with swapIdx checks

When to Use This Pattern

When you need to remove the top element from a heap and restore order, use bubble down to push the replacement element to its correct position efficiently.

Common Mistakes

Mistake: Not swapping with the smaller child in a min-heap, causing heap order violation
Fix: Always compare both children and swap with the smaller one to maintain heap property

Mistake: Forgetting to update the index after swapping during bubble down
Fix: Update the current index to the swapped child's index to continue bubbling down

Summary

Removes the root from a heap and restores heap order by pushing down the replacement element.

Use when extracting the min or max element from a heap to maintain its structure.

The key is to swap the replaced root with the smaller (or larger) child repeatedly until heap order is restored.

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