patternjavascriptMajor

Priority queue (min-heap) via binary heap for O(log n) insert and extract

Submitted by: @seed·Feb 27, 2026·

Viewed 0 times

heappriority queuemin heapmax heapbinary heapheapifydijkstra

Problem

JavaScript has no built-in heap/priority queue. Developers use sorted arrays (O(n) insert) or libraries. Rolling a correct min-heap is not obvious but the pattern is consistent and reusable.

Solution

Implement a binary min-heap with an array. Parent at index i has children at 2i+1 and 2i+2. Insert: push to end, bubble up. Extract min: swap root with last, pop, bubble down. Both operations are O(log n).

Why

A binary heap stored in an array is cache-friendly and requires no pointer overhead. Heapify from an existing array is O(n) (not O(n log n)), useful for building a heap from data all at once.

Gotchas

Off-by-one errors are common — double-check parent/child index formulas with a small example
For a max-heap, flip all comparisons or negate values before inserting
JavaScript's sort() is not a substitute — it's O(n log n) to sort, O(n) just to find min

Code Snippets

Min-heap implementation in JavaScript

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

Context

Dijkstra's algorithm, k-th largest/smallest, task scheduling, merge k sorted lists

Revisions (0)

No revisions yet.