Heap Extract Min or Max Bubble Down in DSA Typescript

Mental Model

When we remove the top value from a heap, we replace it with the last value and then push that value 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 its correct place so the pyramid stays balanced.

      1
     / \
    3   5
   / \ / \
  4  8 6  7

Heap array: [1, 3, 5, 4, 8, 6, 7]
↑ top (root)

Dry Run Walkthrough

Input: Heap array: [1, 3, 5, 4, 8, 6, 7], extract min (remove 1)

Goal: Remove the smallest element (root) and restore heap order by pushing down the last element

Step 1: Remove root 1 and replace it with last element 7

Heap array: [7, 3, 5, 4, 8, 6]
Structure:
      7
     / \
    3   5
   / \ / 
  4  8 6

Why: We remove the top element and move the last element to the root to keep the tree complete

Step 2: Compare 7 with children 3 and 5; swap with smaller child 3

Heap array: [3, 7, 5, 4, 8, 6]
Structure:
      3
     / \
    7   5
   / \ / 
  4  8 6

Why: 7 is bigger than 3, so swap to restore heap order

Step 3: Compare 7 with children 4 and 8; swap with smaller child 4

Heap array: [3, 4, 5, 7, 8, 6]
Structure:
      3
     / \
    4   5
   / \ / 
  7  8 6

Why: 7 is bigger than 4, so swap again to restore heap order

Step 4: Compare 7 with children (none), stop bubbling down

Heap array: [3, 4, 5, 7, 8, 6]
Structure:
      3
     / \
    4   5
   / \ / 
  7  8 6

Why: 7 has no children smaller than itself, heap order restored

Result:

Heap array after extract min and bubble down: [3, 4, 5, 7, 8, 6]

Annotated Code

DSA Typescript

class MinHeap {
  heap: number[];

  constructor(arr: number[]) {
    this.heap = arr;
  }

  extractMin(): number | null {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0 && last !== undefined) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return min;
  }

  bubbleDown(index: number): void {
    const length = this.heap.length;
    let smallest = index;

    while (true) {
      const left = 2 * index + 1;
      const right = 2 * index + 2;

      if (left < length && this.heap[left] < this.heap[smallest]) {
        smallest = left;
      }

      if (right < length && this.heap[right] < this.heap[smallest]) {
        smallest = right;
      }

      if (smallest !== index) {
        [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
        index = smallest;
      } else {
        break;
      }
    }
  }
}

// Driver code
const heap = new MinHeap([1, 3, 5, 4, 8, 6, 7]);
const extracted = heap.extractMin();
console.log("Extracted min:", extracted);
console.log("Heap after extract min and bubble down:", heap.heap.join(", "));

const min = this.heap[0];

Store the root value to return later

const last = this.heap.pop();

Remove last element to replace root

this.heap[0] = last;

Move last element to root position

this.bubbleDown(0);

Restore heap order by pushing down the new root

const left = 2 * index + 1; const right = 2 * index + 2;

Calculate left and right child indices

if (left < length && this.heap[left] < this.heap[smallest]) { smallest = left; }

Find smaller child on left

if (right < length && this.heap[right] < this.heap[smallest]) { smallest = right; }

Find smaller child on right

if (smallest !== index) { swap and update index } else { break; }

Swap with smaller child or stop if heap order restored

Output

Extracted min: 1

Heap after extract min and bubble down: 3, 4, 5, 7, 8, 6

Complexity Analysis

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

Space: O(1) because the operation modifies the heap in place without extra space

vs Alternative: Compared to rebuilding the heap from scratch which is O(n), bubble down is much faster for a single extract operation

Edge Cases

Empty heap

extractMin returns null without error

DSA Typescript

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

Heap with one element

extractMin removes and returns the only element, heap becomes empty

DSA Typescript

const last = this.heap.pop(); if (this.heap.length > 0 && last !== undefined) { ... }

Heap where last element is larger than root

bubbleDown stops immediately as heap order is already valid

DSA Typescript

if (smallest !== index) { ... } else { break; }

When to Use This Pattern

When you need to remove the top element from a heap and maintain heap order, use extract and bubble down to restore the heap efficiently.

Common Mistakes

Mistake: Not replacing the root with the last element before bubbling down
Fix: Always move the last element to the root before starting bubble down

Mistake: Not checking if child indices are within heap bounds before comparing
Fix: Check if left and right child indices are less than heap length before accessing

Mistake: Stopping bubble down too early without swapping when needed
Fix: Continue swapping until the element is in correct position or no smaller child exists

Summary

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

Use when extracting the minimum or maximum element from a heap to maintain its structure.

The key insight is to replace the root with the last element and then push it down to its correct position.