Data Structures & Algorithms · Heap / Priority Queue

Find Median from Data Stream: The Two-Heap Balancing Act

Q: Why use two heaps instead of one sorted structure?

A sorted array gives O(1) median lookups but O(n) inserts, because every insert shifts the tail. Two heaps flip the trade: inserts drop to O(log n) since a heap only sifts one value along a single root-to-leaf path, and the median stays O(1) because it is always one of the two roots. For a long stream, cutting inserts from O(n) to O(log n) is the difference between O(n²) and O(n log n) overall.

Q: How does the algorithm handle even versus odd counts?

The size invariant lets low hold either the same number of elements as high or exactly one more. When the total is odd, that extra element is the true middle, so findMedian returns low.peek(). When the total is even, the two middle values are precisely the two heap roots, so it returns their average, (low.peek() + high.peek()) / 2. The rebalance in addNum guarantees the counts never drift outside that rule.

Q: What is the time and space complexity?

addNum runs in O(log n): one push plus at most one push/pop pair, each a logarithmic heap operation. findMedian runs in O(1) because it only reads the roots. Space is O(n) since every number added is retained across the two heaps. That beats the O(n) per-insert sorted-array baseline and the O(n log n) per-query re-sort approach.

Q: Why push into the max-heap first every time?

Pushing unconditionally into low keeps addNum branch-free at the start — you never decide up front which half a number belongs to. The two correction steps then repair any damage: the ordering check moves the value to high if it is too large, and the size check evens out the counts. Because each correction is a single O(log n) heap operation, starting with a blind push costs nothing and keeps the code uniform.

Solve Find Median from Data Stream with two balanced heaps — a max-heap and min-heap that keep the median at the boundary in O(log n) per insert.

July 17, 20266 min readBy Bhavesh Singh

heapsmax-heapmin-heaprunning medianstreamingheap / priority queue

This article has an interactive companion

Don't just read it — step through it interactively, one state change at a time.

Open the Find Median from Data Stream visualizer

Numbers arrive one at a time, and after each one you must report the median of everything seen so far. There is no final array to sort — the stream never ends, and every query wants an answer now.

The naive move is to keep a list and re-sort it on every query. That works, but sorting n numbers on each of n queries is punishingly slow. The elegant answer splits the data across two heaps so the median is always sitting right at the seam between them, reachable in O(1) with O(log n) inserts.

The problem

Design a MedianFinder class with two operations:

addNum(num) — add an integer from the stream.
findMedian() — return the median of all numbers added so far.

The median is the middle value of the sorted sequence. With an odd count it is the single middle element; with an even count it is the average of the two middle elements.

text

addNum(5)   -> stream: [5]           findMedian() = 5
addNum(15)  -> stream: [5,15]        findMedian() = 10   // (5+15)/2
addNum(1)   -> stream: [1,5,15]      findMedian() = 5
addNum(3)   -> stream: [1,3,5,15]    findMedian() = 4    // (3+5)/2

Notice you never get to see the numbers sorted — you have to maintain order as they trickle in, and answer between every insert.

The brute force baseline

Keep one sorted array. On addNum, insert the value in its correct slot; on findMedian, read the middle.

javascript

class MedianFinder {
  constructor() {
    this.nums = [];
  }

  addNum(num) {
    // binary search for the insert position, then splice
    let lo = 0, hi = this.nums.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.nums[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    this.nums.splice(lo, 0, num); // O(n) shift
  }

  findMedian() {
    const n = this.nums.length;
    const mid = n >> 1;
    return n % 2 ? this.nums[mid] : (this.nums[mid - 1] + this.nums[mid]) / 2;
  }
}

findMedian is a fast O(1) — the array is always sorted. The killer is addNum. Finding the slot is O(log n), but splice has to shift every element after it, which is O(n). Feed in n numbers and you have spent O(n²) total. On a 10⁵-element stream that is ten billion element moves.

The key insight: split at the median

The median only ever depends on the value (or two values) sitting in the middle of the sorted order. You do not need the whole array sorted — you only need fast access to those middle elements.

So cut the data in half:

A max-heap called low holds the smaller half. Its root is the largest of the small numbers.
A min-heap called high holds the larger half. Its root is the smallest of the large numbers.

If you keep two invariants true, the median is trivial:

Ordering — every value in low is <= every value in high. The two roots straddle the median.
Size — the halves differ by at most one element, and low is allowed to be the bigger one.

When the total count is odd, low holds the extra element, so the median is low.peek(). When it is even, the median averages the two roots: (low.peek() + high.peek()) / 2. Both roots are O(1) to read, and each heap insert or extract is O(log n). That is the whole trick.

The optimal solution

Push the newcomer into low first, then run two cheap corrections — one to restore ordering, one to restore the size balance. This mirrors the visualizer's addNum exactly.

javascript

class MedianFinder {
  constructor() {
    this.low = new MaxHeap();  // lower half — root is the largest small value
    this.high = new MinHeap(); // upper half — root is the smallest large value
  }

  addNum(num) {
    // 1. Add to max heap (lower half) by default
    this.low.push(num);

    // 2. Fix ordering: the largest of low must not exceed the smallest of high
    if (this.low.size() > 0 && this.high.size() > 0 &&
        this.low.peek() > this.high.peek()) {
      this.high.push(this.low.pop());
    }

    // 3. Fix sizes: keep |low - high| <= 1, with low allowed to be bigger
    if (this.low.size() > this.high.size() + 1) {
      this.high.push(this.low.pop());
    } else if (this.high.size() > this.low.size()) {
      this.low.push(this.high.pop());
    }
  }

  findMedian() {
    if (this.low.size() > this.high.size()) {
      return this.low.peek();          // odd total — middle lives in low
    }
    return (this.low.peek() + this.high.peek()) / 2.0; // even total
  }
}

Why push into low first and then fix? Inserting unconditionally keeps the logic uniform — you never branch on where the number belongs. The two correction steps run in a fixed order: enforce the ordering property, then rebalance the counts. Each step is at most one push plus one pop, so addNum stays O(log n).

Walkthrough

Trace the stream [5, 15, 1, 3]. Watch the two heaps after each addNum, and how the rebalance keeps the median at the boundary.

addNum	After push to low	Rebalance step	low (max-heap)	high (min-heap)	findMedian
5	low=[5]	sizes 1 vs 0 — fine	[5]	[]	5 (odd → low.peek)
15	low=[15,5]	low too big → pop 15 to high	[5]	[15]	10 = (5+15)/2
1	low=[5,1]	5 ≤ 15, sizes 2 vs 1 — fine	[5,1]	[15]	5 (odd → low.peek)
3	low=[5,3,1]	low too big → pop 5 to high	[3,1]	[5,15]	4 = (3+5)/2

Step through it: adding 15 makes low hold two while high holds none, so rule 3 shoves the root 15 over to high. Adding 3 again overfills low (three vs one), so its root 5 migrates up. After every insert the roots — low.peek() and high.peek() — sit exactly on either side of the median. No element is ever more than one heap-level away from where it needs to be.

Complexity

Approach	Time (addNum)	Time (findMedian)	Space	Why
Sorted array + splice	O(n)	O(1)	O(n)	inserting shifts every later element
Re-sort on each query	O(1)	O(n log n)	O(n)	sorting the whole list per median
Two heaps	O(log n)	O(1)	O(n)	one heap push/pop; roots read directly

addNum does at most two heap operations, each O(log n). findMedian just peeks one or two roots, so it is O(1). Space is O(n) — every number is stored across the two heaps.

Common mistakes

Skipping the ordering check. Pushing into low without step 2 lets a large number sit in the lower half. The next size-rebalance then moves the wrong value across, and roots stop straddling the median.
Letting high grow bigger than low. The size rule is asymmetric: low may exceed high by one, never the reverse. findMedian returns low.peek() for odd counts, so the extra element must live in low.
Averaging with integer math. For even counts, (low.peek() + high.peek()) / 2 must be floating-point division. Integer division truncates (3+5)/2 correctly here but silently breaks on odd sums like (3+4)/2 = 3.5.
Reusing a min-heap for both halves. The lower half needs a max-heap so its root is the largest small value. Using two min-heaps loses O(1) access to the small side's boundary.

Where this pattern shows up next

The dual-heap and single-heap ideas power a whole family of streaming and top-k problems:

Min-Heap Operations — the primitive under everything here: push, pop, and sift in O(log n).
Kth Largest Element in an Array — a size-k min-heap that keeps the k biggest values on hand.
Kth Largest Element in a Stream — the same bounded heap, maintained live as numbers arrive.
Kth Smallest Element in a Sorted Matrix — a heap that merges sorted rows to pull ordered elements one at a time.

You can also step through Find Median from Data Stream interactively and watch values migrate between the two heaps as the balance tips.

FAQ

Why use two heaps instead of one sorted structure?

A sorted array gives O(1) median lookups but O(n) inserts, because every insert shifts the tail. Two heaps flip the trade: inserts drop to O(log n) since a heap only sifts one value along a single root-to-leaf path, and the median stays O(1) because it is always one of the two roots. For a long stream, cutting inserts from O(n) to O(log n) is the difference between O(n²) and O(n log n) overall.

How does the algorithm handle even versus odd counts?

The size invariant lets low hold either the same number of elements as high or exactly one more. When the total is odd, that extra element is the true middle, so findMedian returns low.peek(). When the total is even, the two middle values are precisely the two heap roots, so it returns their average, (low.peek() + high.peek()) / 2. The rebalance in addNum guarantees the counts never drift outside that rule.

What is the time and space complexity?

addNum runs in O(log n): one push plus at most one push/pop pair, each a logarithmic heap operation. findMedian runs in O(1) because it only reads the roots. Space is O(n) since every number added is retained across the two heaps. That beats the O(n) per-insert sorted-array baseline and the O(n log n) per-query re-sort approach.

Why push into the max-heap first every time?

Pushing unconditionally into low keeps addNum branch-free at the start — you never decide up front which half a number belongs to. The two correction steps then repair any damage: the ordering check moves the value to high if it is too large, and the size check evens out the counts. Because each correction is a single O(log n) heap operation, starting with a blind push costs nothing and keeps the code uniform.

Make it stick: run this one yourself

Don't just read it — step through it interactively, one state change at a time.

Open the Find Median from Data Stream visualizer

The problem#

The brute force baseline#

The key insight: split at the median#

The optimal solution#

Walkthrough#

Complexity#

Common mistakes#

Where this pattern shows up next#

FAQ#

Why use two heaps instead of one sorted structure?#

How does the algorithm handle even versus odd counts?#

What is the time and space complexity?#

Why push into the max-heap first every time?#

Related articles