Two Heaps

Two Heaps

Maintain a max-heap for the lower half and a min-heap for the upper half of a stream.

When to use

Find median of a stream, sliding window median, schedule tasks with priority.

Complexity
time O(log n) per insertion, O(1) for median queryspace O(n)

Each new value pushes into one heap and may rebalance the other, both log n operations. The medians sit at the top of each heap for O(1) reads. Both heaps together hold all n values.

max-heap (low)min-heap (high)97481012med
Max-heap on the low half, min-heap on the high half. Median sits at the rims.
How it works

Two heaps maintain a partition of a stream into a 'low half' (max-heap) and 'high half' (min-heap). The invariant is that every element in low is <= every element in high, and the sizes differ by at most one. The median is then either the top of the larger heap or the average of the two tops.

Insertion is O(log n): push to one heap, then rebalance by moving the top of the larger to the smaller if the size invariant is violated. The trick is choosing which heap to push to first — a common pattern is to push to low (max-heap), then move low's top to high, then if high is now larger, move high's top back to low. This guarantees both the value invariant and size invariant.

The pattern generalizes beyond medians: any 'middle element' or 'kth-from-median' query over a stream benefits. Sliding window median adds the wrinkle of removal — standard heaps don't support efficient arbitrary removal, so you either use a TreeMap/SortedList or 'lazy deletion' with a hash map of pending removals.

Key insight

Splitting the data into low/high halves with the invariant max(low) <= min(high) reduces the median query from O(n log n) sorting per insert to O(log n) per insert and O(1) for the query itself.

Common pitfalls
  • Forgetting to negate values when simulating a max-heap in languages with min-heap-only libraries (Python's heapq).
  • Rebalancing only by size and not by value, allowing an element in low that's larger than something in high.
  • Computing the median as integer division on odd counts, truncating .5 incorrectly.
  • In sliding window median, naively removing from a heap in O(n) instead of using lazy deletion or a balanced BST.
  • Allowing the heaps' sizes to differ by 2 or more before rebalancing, causing the median formula to be wrong.
Variations
  • Median of data stream: classic two-heap.
  • Sliding window median: two heaps + lazy deletion via a hash map of invalidated entries.
  • IPO / maximize capital: two heaps where one is min-heap by cost (gating) and the other is max-heap by profit (selecting).
  • Find right interval / schedule problems: heaps keyed by different fields of the same record.
Template
PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
PriorityQueue<Integer> upper = new PriorityQueue<>(); // min-heap

void add(int num) {
    if (lower.isEmpty() || num <= lower.peek()) lower.offer(num);
    else upper.offer(num);
    // rebalance so |lower| - |upper| in {0, 1}
    if (lower.size() > upper.size() + 1) upper.offer(lower.poll());
    else if (upper.size() > lower.size()) lower.offer(upper.poll());
}

double median() {
    if (lower.size() > upper.size()) return lower.peek();
    return (lower.peek() + upper.peek()) / 2.0;
}

Problems using this pattern

2

Easiest first · Blind 75 above NeetCode 150

Practice these problems
Solve mode — formulate the approach, then reveal. 2 problems.