Two Heaps Pattern

CodingSenior2 min read · 2 problemsUpdated Oct 28, 2026

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

When to Use It

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

Classic example: Find median from data stream.

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.

Max-heap on the low half, min-heap on the high half. Median sits at the rims.

Templates

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;
}

import heapq

lower = []  # max-heap (store negatives)
upper = []  # min-heap

def add(num):
    if not lower or num <= -lower[0]:
        heapq.heappush(lower, -num)
    else:
        heapq.heappush(upper, num)
    # rebalance
    if len(lower) > len(upper) + 1:
        heapq.heappush(upper, -heapq.heappop(lower))
    elif len(upper) > len(lower):
        heapq.heappush(lower, -heapq.heappop(upper))

def median():
    if len(lower) > len(upper):
        return -lower[0]
    return (-lower[0] + upper[0]) / 2.0

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 binary search tree (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.

Big O

Time: O(log n) per insertion, O(1) for median query
Space: 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.

Next PatternSubsets (BFS-style generation)