Running Median with Two Heaps

The running median is one of the most elegant two-heap problems. You cannot sort a stream in advance, yet you need the median after every insertion. Maintaining two heaps solves it in O(log n) per insertion and O(1) per read.

The Idea

Partition the stream into two halves at the median:

• lo — a max-heap holding the lower half. Its root is the largest small number.
• hi — a min-heap holding the upper half. Its root is the smallest large number.

Invariant: lo.size is either equal to or one greater than hi.size.

When the invariant holds, reading the median is instant:

• If sizes are equal: median = (lo.peek() + hi.peek()) / 2
• If lo is larger: median = lo.peek()

Insertion and Rebalancing

class MedianFinder {
  // lo: max-heap (negate values to simulate with a min-heap)
  #lo = new MinHeap();
  // hi: standard min-heap
  #hi = new MinHeap();

  addNum(num) {
    // 1. Route the new number to the correct half
    if (this.#lo.size === 0 || num <= -this.#lo.peek()) {
      this.#lo.push(-num);   // negate to turn MinHeap into MaxHeap
    } else {
      this.#hi.push(num);
    }

    // 2. Rebalance: lo must be equal or one larger than hi
    if (this.#lo.size > this.#hi.size + 1) {
      this.#hi.push(-this.#lo.pop());
    } else if (this.#hi.size > this.#lo.size) {
      this.#lo.push(-this.#hi.pop());
    }
  }

  findMedian() {
    if (this.#lo.size === this.#hi.size) {
      return (-this.#lo.peek() + this.#hi.peek()) / 2;
    }
    return -this.#lo.peek(); // lo always holds the extra element
  }
}

const mf = new MedianFinder();
[5, 2, 3, 4, 1].forEach((n, i) => {
  mf.addNum(n);
  console.log(`After ${n}: median = ${mf.findMedian()}`);
});
// After 5: 5
// After 2: 3.5
// After 3: 3
// After 4: 3.5
// After 1: 3

Why Negate for a Max-Heap?

JavaScript has no built-in max-heap. A MinHeap returns the smallest value; storing -num makes the most negative value (i.e. the largest original number) the root. Negate again on the way out to recover the real value.

Complexity

Sorting the entire stream for each query is O(n log n) per call. The two-heap approach pays O(log n) once when the number arrives and O(1) every time the median is read — ideal for dashboards, analytics pipelines, or interview-style streaming problems.

Rebalancing at a Glance

Up Next

Put heap knowledge to work in graph algorithms — shortest paths, spanning trees, and more — where priority queues are an indispensable building block.