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.