← Index

Trees & Heaps

Heap (Priority Queue)

A tree where the smallest (or biggest) item is always on top.

What it is

A binary heap keeps every parent smaller than its children (min-heap) or bigger (max-heap), stored flat in an array using index math instead of pointers. You get O(1) peek at the min/max and O(log n) insert/remove — it's the structure behind every 'priority queue': process the most urgent thing next, not the thing that arrived first.

Real-world examples

• A hospital ER — patients are seen by severity of condition, not by arrival order. The most critical case is always 'on top'.
• A to-do list sorted by deadline where you always work the most urgent item next, and new items slot in without re-sorting everything.

Where you've probably used this already

• Dijkstra's algorithm (see dijkstra.js) uses a min-heap to always expand the closest unvisited node next.
• "Top K" / "K most frequent elements" interview problems — a heap avoids fully sorting when you only need the top few.
• OS/task schedulers and JS engine microtask-style scheduling that need 'run the most urgent thing next'.

Complexity

Code

// Binary Heap (Min-Heap) — a tree stored in a flat array where every
// parent is smaller than its children. Gives O(1) peek at the smallest
// item and O(log n) insert/remove. Powers priority queues.
//
// Array trick: for a node at index i,
//   left child  = 2i + 1
//   right child = 2i + 2
//   parent      = Math.floor((i - 1) / 2)

class MinHeap {
  constructor() {
    this.values = [];
  }

  insert(value) {
    this.values.push(value);
    this._bubbleUp();
  }

  _bubbleUp() {
    let idx = this.values.length - 1;
    while (idx > 0) {
      const parentIdx = Math.floor((idx - 1) / 2);
      if (this.values[idx] >= this.values[parentIdx]) break;
      [this.values[idx], this.values[parentIdx]] = [
        this.values[parentIdx],
        this.values[idx],
      ];
      idx = parentIdx;
    }
  }

  // Remove and return the smallest value
  extractMin() {
    const min = this.values[0];
    const last = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = last;
      this._sinkDown();
    }
    return min;
  }

  _sinkDown() {
    let idx = 0;
    const length = this.values.length;
    while (true) {
      const left = 2 * idx + 1;
      const right = 2 * idx + 2;
      let smallest = idx;

      if (left < length && this.values[left] < this.values[smallest]) {
        smallest = left;
      }
      if (right < length && this.values[right] < this.values[smallest]) {
        smallest = right;
      }
      if (smallest === idx) break;

      [this.values[idx], this.values[smallest]] = [
        this.values[smallest],
        this.values[idx],
      ];
      idx = smallest;
    }
  }

  peek() {
    return this.values[0];
  }
}

// --- Example Usage ---
const heap = new MinHeap();
[9, 4, 7, 1, 3].forEach((n) => heap.insert(n));

console.log("Heap array (not fully sorted, just heap-ordered):", heap.values);
console.log("Peek (smallest):", heap.peek()); // 1

const sorted = [];
while (heap.values.length) sorted.push(heap.extractMin());
console.log("Extracted in order:", sorted); // [1,3,4,7,9]

// Real uses of this exact structure:
// - JS's Promise scheduler / OS task schedulers (run soonest deadline first)
// - Dijkstra's algorithm (always expand the closest unvisited node)
// - "top K" / "K most frequent" style interview problems