jsschools

Min-Heap

A heap where the root is always the minimum element, enabling O(1) access to the smallest value and O(log n) extract-min.

Spec ↗

Syntax

class MinHeap extends Heap {
  constructor() { super((a, b) => a - b); }
}

Returns

MinHeap — A new Min-Heap instance where the minimum element is always at the top.

Examples

class MinHeap {
  #d = [];
  push(v) { this.#d.push(v); this.#up(this.#d.length - 1); }
  pop() {
    const top = this.#d[0];
    const last = this.#d.pop();
    if (this.#d.length) { this.#d[0] = last; this.#down(0); }
    return top;
  }
  peek() { return this.#d[0]; }
  get size() { return this.#d.length; }
  #up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.#d[p] <= this.#d[i]) break;
      [this.#d[i], this.#d[p]] = [this.#d[p], this.#d[i]]; i = p;
    }
  }
  #down(i) {
    const n = this.#d.length;
    while (true) {
      let s = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.#d[l] < this.#d[s]) s = l;
      if (r < n && this.#d[r] < this.#d[s]) s = r;
      if (s === i) break;
      [this.#d[i], this.#d[s]] = [this.#d[s], this.#d[i]]; i = s;
    }
  }
}

// K smallest numbers from a stream
const heap = new MinHeap();
[9, 4, 7, 1, 5, 3].forEach(n => heap.push(n));
const k3 = [heap.pop(), heap.pop(), heap.pop()];
console.log(k3);
Output 
[ 1, 3, 4 ]

// Dijkstra's shortest path uses a min-heap priority queue
function dijkstra(graph, start) {
  const dist = {};
  const pq = new MinHeap(); // stores [distance, node]
  // ... (abbreviated)
  pq.push([0, start]);
  while (pq.size > 0) {
    const [d, u] = pq.pop();
    if (dist[u] !== undefined) continue;
    dist[u] = d;
    for (const [v, w] of graph[u] ?? []) pq.push([d + w, v]);
  }
  return dist;
}
console.log('min-heap powers Dijkstra O((V+E) log V)');
Output 
min-heap powers Dijkstra O((V+E) log V)

Notes

| Operation | Best | Avg | Worst | Space | |-----------|------|---------|---------|-------| | Peek min | O(1) | O(1) | O(1) | O(1) | | Push | O(1) | O(log n)| O(log n)| O(1) | | Pop min | O(log n)| O(log n)|O(log n)| O(1) | | Build | O(n) | O(n) | O(n) | O(n) | Min-heap is the underlying data structure for a min-priority queue. To find the k-th largest element, maintain a min-heap of size k — the top is always the kth-largest seen so far.

See also