Two Heaps

What the two heaps pattern is

Split a growing collection into two halves around its middle: a MAX-heap holding the smaller half (its root = the largest small element) and a MIN-heap holding the larger half (its root = the smallest large element). The median then lives at the roots: with odd count it is the bigger heap's root; with even count, the average of both roots. Every element in the low heap is <= every element in the high heap - that cross-heap invariant is the pattern.

It solves what a single heap cannot: a heap surfaces only its extreme, but the median is the middle. Two heaps facing each other turn 'the middle' into 'the extremes of two halves'.

How to recognize it

Signals: 'median of a data stream', 'running median over a sliding window', percentile tracking, or any need for the k-th ordered element of a live collection where both smaller and larger elements keep arriving. Also scheduling problems juggling two priorities at once (IPO: cheapest affordable project vs. most profitable available one) - one heap per priority, elements migrating between them.

The test: do you need an ORDER STATISTIC (middle, percentile) of data that changes, or the best element under two different orderings at different moments? Either answer points here.

The add-then-rebalance template

Two invariants after every insertion: ordering (max of low <= min of high) and size (low holds equal count or exactly one more). The bulletproof insertion: always push into low first, then move low's root to high (restores ordering unconditionally), then if high outgrew low, move high's root back. Three heap operations worst case, no branching on the value.

low  = max-heap   # smaller half
high = min-heap   # larger half

def add(x):
    low.push(x)
    high.push(low.pop())          # ordering restored
    if len(high) > len(low):
        low.push(high.pop())      # size restored

def median():
    if len(low) > len(high): return low.peek()
    return (low.peek() + high.peek()) / 2

Complexity

Insertion is O(log n) (a constant number of heap operations); median reads are O(1). For n stream elements: O(n log n) total, O(n) memory. The sliding-window variant needs element removal, which vanilla heaps lack - lazy deletion (tombstone map, purge stale roots on read) keeps the same asymptotics; order-statistic trees are the heavyweight alternative.

Common pitfalls

Max-heap direction: the LOW half needs a max-heap. In min-heap-only languages, negate values going in and out of low - and be disciplined about where the negation happens.

Branching insertions ('if x < low.peek() push low else push high') that skip rebalancing - sizes drift and the median reads garbage. The push-through version cannot drift.

Choosing which heap may be larger and then reading the median from the other one - pick 'low may hold one extra' and read odd-count medians from low, consistently.

Integer overflow in (a + b) / 2 for extreme values - compute low + (high - low) / 2 or use wider types.

Sliding windows: removing an arbitrary element from a heap is O(n) done naively - lazy deletion with a counted tombstone map is the expected answer, including the purge-before-peek step.

Worked examples

add(x):
    low.push(x)
    high.push(low.pop())
    if len(high) > len(low): low.push(high.pop())

median():
    return len(low) > len(high)
        ? low.peek()
        : (low.peek() + high.peek()) / 2

for each new element: add(x) as in stream-median
for each departing element d:
    tombstones[d] += 1
    decrement logical size of the half d belongs to
    rebalance by logical sizes
before any peek:
    while tombstones[heap.top] > 0:
        tombstones[heap.top] -= 1; heap.pop()

byCapital = min-heap of (capital, profit) for all projects
byProfit = max-heap
repeat k times:
    while byCapital not empty and byCapital.top.capital <= w:
        byProfit.push(byCapital.pop().profit)
    if byProfit empty: break
    w += byProfit.pop()
return w

Check yourself

Try to answer before revealing - retrieving from memory is what makes it stick.

Frequently asked questions