Heap

Efficient for getting the min (or max) element repeatedly. Used in priority queues, Dijkstra’s algorithm, etc.

class MinHeap {
  items: number[];

  constructor() {
    this.items = [];
  }

  // Add item and bubble up
  insert(value: number): void {
    this.items.push(value);
    this.bubbleUp(this.items.length - 1);
  }

  // Remove and return smallest item
  extractMin(): number | undefined {
    if (this.items.length === 0) return undefined;
    if (this.items.length === 1) return this.items.pop();

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

  // Helper: bubble up to maintain heap property
  private bubbleUp(index: number): void {
    const parent = Math.floor((index - 1) / 2);
    if (index > 0 && this.items[index]! < this.items[parent]!) {
      [this.items[index]!, this.items[parent]!] = [this.items[parent]!, this.items[index]!];
      this.bubbleUp(parent);
    }
  }

  // Helper: bubble down to maintain heap property
  private bubbleDown(index: number): void {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let smallest = index;

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

    if (smallest !== index) {
      [this.items[index]!, this.items[smallest]!] = [this.items[smallest]!, this.items[index]!];
      this.bubbleDown(smallest);
    }
  }
}

const heap = new MinHeap();
heap.insert(3);
heap.insert(1);
heap.insert(4);
console.log(heap.extractMin()); // 1
console.log(heap.extractMin()); // 3

---