Two Heaps Pattern

When to use Two Heaps

• You need to maintain the median of a stream of numbers as new values arrive.
• You need to track the running median of a sliding window over an array.
• The problem asks for the smallest k elements out of one set combined with the largest k elements out of another.
• You repeatedly pick from two separate ordered collections and need the cheapest or most valuable element on each turn.
• You can split data into a `low` half and a `high` half and query the boundary value in O(1).

Template

class MedianFinder {
  constructor() {
    this.low = new MaxHeap();
    this.high = new MinHeap();
  }
  addNum(num) {
    if (this.low.size === 0 || num <= this.low.peek()) {
      this.low.push(num);
    } else {
      this.high.push(num);
    }
    if (this.low.size > this.high.size + 1) this.high.push(this.low.pop());
    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();
    return (this.low.peek() + this.high.peek()) / 2;
  }
}

Common mistakes

• Forgetting to invert comparisons when implementing a max-heap on top of a standard min-heap library, leading to a min-of-min instead of max-of-low.
• Letting the size difference grow beyond one — the median is only readable in O(1) when the heaps are balanced.
• Returning the wrong heap's top on even total counts; the answer is the average of both tops, not just one.
• Mixing integer and float division when computing the average median, which truncates the result in some languages.
• On Sliding Window Median, lazily deleting outgoing elements without a synced count, leading to a heap top that no longer belongs to the window.