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.

Practice

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

easy

A. To delete the last element in the heap

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

C. To swap the minimum element with the maximum element

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

Solution

1. Step 1: Understand extract-min operation

   When the minimum element (root) is removed, the last element replaces the root.

2. Step 2: Apply bubble down to restore heap

   The bubble down moves this element down the tree to restore the min-heap property.

3. Final Answer:

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

4. Quick Check:

   Bubble down fixes heap after extract-min [OK]

Hint: Bubble down fixes heap after removing root [OK]

Common Mistakes:

• Confusing bubble down with insertion
• Thinking bubble down swaps min and max
• Assuming bubble down deletes elements

2. Which of the following TypeScript code snippets correctly swaps two elements in a heap array during bubble down?

easy

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

B. const temp = heap[i]; heap[i] = heap[j]; heap[j] = temp;

C. swap(heap[i], heap[j]);

D. heap[i] = heap[j]; heap[j] = heap[i];

Solution

1. Step 1: Check valid swap syntax in TypeScript

   const temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; uses a temporary variable to swap two elements correctly.

2. Step 2: Identify incorrect syntax in other options

   heap[i], heap[j] = heap[j], heap[i]; uses Python-style unpacking (invalid in TypeScript), C calls undefined function, D overwrites values incorrectly.

3. Final Answer:

   const temp = heap[i]; heap[i] = heap[j]; heap[j] = temp; -> Option B

4. Quick Check:

   Use temp variable to swap in TypeScript [OK]

Hint: Use temp variable for swapping in TypeScript [OK]

Common Mistakes:

• Using Python tuple swap syntax in TypeScript
• Calling undefined swap function
• Overwriting values without temp variable

3. Consider the min-heap array [2, 5, 3, 10, 7]. After extracting the minimum element and performing bubble down, what is the resulting heap array?

medium

A. [3, 5, 7, 10]

B. [3, 7, 5, 10]

C. [5, 7, 3, 10]

D. [7, 5, 3, 10]

Solution

1. Step 1: Remove root and replace with last element

   Remove 2, replace root with 7: [7, 5, 3, 10]

2. Step 2: Bubble down 7 to restore min-heap

   Compare 7 with children 5 and 3; swap with smallest child 3: [3, 5, 7, 10]

3. Final Answer:

   [3, 5, 7, 10] -> Option A

4. Quick Check:

   Extract min and bubble down result = [3, 5, 7, 10] [OK]

Hint: Replace root with last, then bubble down [OK]

Common Mistakes:

• Not replacing root with last element
• Swapping with wrong child during bubble down
• Forgetting to remove last element

4. The following TypeScript code attempts to bubble down an element in a max-heap but does not work correctly. What is the main bug?

function bubbleDown(heap: number[], i: number) {
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  let largest = i;

  if (left < heap.length && heap[left] > heap[largest]) {
    largest = left;
  }
  if (right < heap.length && heap[right] > heap[largest]) {
    largest = right;
  }

  if (largest !== i) {
    heap[i] = heap[largest];
    heap[largest] = heap[i];
    bubbleDown(heap, largest);
  }
}

medium

A. Swapping elements overwrites values incorrectly without a temporary variable

B. The indices for left and right children are calculated incorrectly

C. The recursive call should be bubbleUp instead of bubbleDown

D. The condition to check children is reversed for max-heap

Solution

1. Step 1: Analyze swap logic in code

   The swap uses heap[i] = heap[largest]; heap[largest] = heap[i]; which overwrites heap[i] before assigning heap[largest].

2. Step 2: Identify correct swap method

   Swapping requires a temporary variable to avoid overwriting values.

3. Final Answer:

   Swapping elements overwrites values incorrectly without a temporary variable -> Option A

4. Quick Check:

   Swap needs temp variable to avoid overwrite [OK]

Hint: Always use temp variable when swapping array elements [OK]

Common Mistakes:

• Overwriting values during swap without temp
• Confusing bubbleDown with bubbleUp
• Incorrect child index calculations

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

hard

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

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

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

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

Solution

1. Step 1: Remove max (root) and replace with last element

   Remove 50, replace root with 35: [35, 30, 40, 10, 20]

2. Step 2: Bubble down 35 to restore max-heap

   Compare 35 with children 30 and 40; swap with largest child 40: [40, 30, 35, 10, 20]

3. Final Answer:

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

4. Quick Check:

   Extract max and bubble down result = [40, 30, 35, 10, 20] [OK]

Hint: Replace root with last, then bubble down largest child [OK]

Common Mistakes:

• Swapping with wrong child during bubble down
• Not removing last element after replacement
• Confusing min-heap bubble down with max-heap