Two Heaps

How It Works

The two-heaps pattern maintains two priority queues that split your dataset roughly in half: a max-heap holding the smaller half of the values (so its top is the largest of the small numbers) and a min-heap holding the larger half (so its top is the smallest of the large numbers). Together, the two tops sit right next to the midpoint of the whole dataset.

Every insert follows the same three steps: push the new value into one heap, then rebalance by moving the top of one heap into the other if a value ended up on the wrong side, and finally re-balance sizes so neither heap has more than one extra element over the other. Because heap push/pop is O(log n), you get an O(log n) update instead of an O(n log n) re-sort on every new element. That's the entire reason this pattern exists.

Once the heaps are balanced, reading the median (or the boundary value) is O(1): if the heaps are the same size, average the two tops; if one heap has an extra element, its top is the answer.

When To Use It

• Streaming median: numbers arrive one at a time and you must report the median after each one, with no ability to re-sort from scratch.
• Running order statistics: you need the "middle" element (or the kth-from-middle) of a collection that keeps growing.
• Scheduling / interval overlap: track how many meetings or resources are active at once by pushing start times into a min-heap of end times and popping whenever a new interval starts after the earliest end time.
• Two-sided greedy selection: when you need efficient access to both "smallest available" and "largest available" at the same time, such as picking the most profitable project you can currently afford (IPO-style problems).
• Naive re-sort would be too slow: if your instinct is "sort the array again after every update," that's the signal to reach for two heaps instead.

Time & Space Complexity

Each insert costs O(log n) for the heap push and, in the worst case, one pop-and-push to rebalance, still O(log n). Reading the median or boundary value is O(1) since it's just the heap tops. Space is O(n) to hold every element across both heaps. For n total insertions, the whole stream costs O(n log n), versus O(n² log n) if you re-sorted after every single insert.

// Two-heaps template: max-heap for the lower half, min-heap for the upper half
class TwoHeapMedian {
  constructor() {
    this.small = new MaxHeap(); // lower half, largest on top
    this.large = new MinHeap(); // upper half, smallest on top
  }

  addNum(num) {
    // 1. Push into the correct side first
    if (this.small.size() === 0 || num <= this.small.peek()) {
      this.small.push(num);
    } else {
      this.large.push(num);
    }

    // 2. Rebalance so sizes never differ by more than 1
    if (this.small.size() > this.large.size() + 1) {
      this.large.push(this.small.pop());
    } else if (this.large.size() > this.small.size() + 1) {
      this.small.push(this.large.pop());
    }
  }

  findMedian() {
    if (this.small.size() === this.large.size()) {
      return (this.small.peek() + this.large.peek()) / 2;
    }
    return this.small.size() > this.large.size() ? this.small.peek() : this.large.peek();
  }
}

Alternative Approaches

• Sorted array / binary search insert: keep one sorted array and binary-search for the insert position. Lookup of the median is O(1), but insertion is O(n) due to shifting, so it loses to two heaps as the stream grows.
• Balanced BST / order-statistics tree: gives O(log n) insert and O(log n) rank queries, and generalizes better if you need arbitrary percentiles, not just the median. More complex to implement from scratch than two heaps.
• Bucket / counting approach: if values are bounded integers, a Fenwick tree (BIT) over value buckets can answer "kth smallest so far" in O(log n) and is often faster in practice than heaps for that constrained case.
• Single heap with lazy deletion: for sliding-window variants (like Sliding Window Median), pair the two heaps with hash sets tracking "stale" values so you can lazily skip elements that fell out of the window instead of removing them immediately.

Common Mistakes

• Forgetting to rebalance sizes: pushing into whichever heap is "correct" by value but never keeping |size(small) - size(large)| <= 1 breaks the O(1) median read.
• Using the wrong heap type: mixing up which side needs a max-heap vs a min-heap silently flips comparisons and produces wrong medians.
• Off-by-one on odd vs even total count: not handling the case where one heap legitimately has one more element than the other.
• Rebuilding heaps from scratch on every update: defeats the entire purpose of the pattern; only the newest element should move.
• Ignoring duplicate removal in sliding-window variants: without lazy deletion or a matching hash map, elements that should have expired from the window keep influencing the answer.

Pattern Summary

Reach for two heaps whenever you need fast, repeated access to the "middle" or "boundary" of a growing or streaming dataset: median-of-stream, k-th order statistics, and greedy resource/interval problems all reduce to keeping a max-heap of the small half and a min-heap of the large half in sync. The payoff is O(log n) updates with O(1) reads, which is what separates a passing streaming-median solution from one that times out.