Min Heap

Min Heap

A Min Heap is a complete binary tree where every parent node is smaller than or equal to its children. The smallest element is always at the root.

Array Representation

A binary heap is stored as a flat array. For a node at index i:

• Left child: 2 * i + 1
• Right child: 2 * i + 2
• Parent: Math.floor((i - 1) / 2)

        1
       / \
      3    5
     / \
    7    9

Array: [1, 3, 5, 7, 9]

Insert (Bubble Up)

1. Push the new value to the end of the array.
2. Compare it with its parent — if smaller, swap them.
3. Repeat until the heap property is restored.

insert(val) {
  this.data.push(val);
  let i = this.data.length - 1;
  while (i > 0) {
    const parent = Math.floor((i - 1) / 2);
    if (this.data[i] >= this.data[parent]) break;
    [this.data[i], this.data[parent]] = [this.data[parent], this.data[i]];
    i = parent;
  }
}

Extract Min (Bubble Down)

1. Save the root (minimum).
2. Move the last element to the root.
3. Compare with children — swap with the smaller child if needed.
4. Repeat until the heap property is restored.

extractMin() {
  if (this.data.length === 0) return undefined;
  const min = this.data[0];
  const last = this.data.pop();
  if (this.data.length > 0) {
    this.data[0] = last;
    // bubble down from index 0
  }
  return min;
}

Complexity

Your Task

Implement a MinHeap class with insert, extractMin, and peek methods.