Two Heaps

At a glance

The instinct

A single heap only tells you about one extreme: the smallest or the largest. Many problems care about the boundary between two groups instead: the median of a stream, the middle of a sliding window, or "the most profitable project I can currently afford". Two heaps put that boundary on top of both heaps at once.

Think of the data as sorted and then cut in half. The left half goes into a max-heap, so its biggest value (the left edge of the cut) is on top. The right half goes into a min-heap, so its smallest value (the right edge of the cut) is on top. Whatever sits at the cut is now readable in O(1) and maintainable in O(log n).

Recognise it

Not this pattern if...

• You need the k-th largest for a fixed k: one heap of size k is enough (Top-K pattern).
• Data is static and you need the median once: sort or quickselect.
• You merge several already-sorted lists: that is K-Way Merge.
• You need arbitrary rank queries over a value range with updates: a Fenwick or segment tree fits better.

Memory hack

Analogy: a see-saw with two kids. The left kid holds the lighter half of the numbers, the right kid the heavier half. After every new number you add it to one side and, if one side gets more than one extra, hand the edge number across. The pivot of the see-saw is the median.

Say it out loud in the interview:

1. "Low half goes in a max-heap, high half in a min-heap; every low value is at most every high value."
2. "Insert, then rebalance so sizes differ by at most one, with the extra on the low side."
3. "The answer is the low top (odd count) or the average of both tops (even count)."

How it works

Every insert follows the same two-step dance: route the value through one heap so ordering stays correct, then rebalance sizes. A neat trick is to always push into low, move low's top to high, and if high became bigger, move its top back. That guarantees both invariants with no if-chains.

Trace for the stream 5, 2, 8, 3:

For Sliding Window Median you must also remove the element leaving the window. Java's PriorityQueue.remove(Object) is O(k), which is usually fine for interviews; the faster option is lazy deletion: record the outgoing value in a "to delete" map, adjust a logical size counter, and discard it only when it surfaces at a heap top.

For IPO, the two heaps play different roles: a min-heap of projects keyed by required capital, and a max-heap of profits for the projects you can afford. Each round, move every newly affordable project across, then take the best profit.

Java template

import java.util.*;

class MedianKeeper {
    private final PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
    private final PriorityQueue<Integer> high = new PriorityQueue<>();                            // min-heap

    public void add(int x) {
        low.offer(x);
        high.offer(low.poll());                 // route the biggest small value to the high side
        if (high.size() > low.size()) {
            low.offer(high.poll());             // keep low.size() == high.size() or +1
        }
    }

    public void remove(int x) {                 // O(n) removal; swap for lazy deletion if needed
        if (!low.isEmpty() && x <= low.peek()) low.remove(x); else high.remove(x);
        if (low.size() > high.size() + 1) high.offer(low.poll());
        else if (high.size() > low.size()) low.offer(high.poll());
    }

    public double median() {
        if (low.size() > high.size()) return low.peek();
        return ((long) low.peek() + high.peek()) / 2.0;   // long avoids int overflow
    }
}

class TwoPoolGreedy {
    // "Unlock then pick best": e.g. projects gated by capital, value = profit
    static long pickBest(int rounds, long budget, int[] cost, int[] value) {
        int n = cost.length;
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> Integer.compare(cost[a], cost[b]));   // locked pool, cheapest first
        PriorityQueue<Integer> ready = new PriorityQueue<>((a, b) -> Integer.compare(value[b], value[a]));
        int p = 0;
        for (int r = 0; r < rounds; r++) {
            while (p < n && cost[idx[p]] <= budget) ready.offer(idx[p++]); // unlock everything affordable
            if (ready.isEmpty()) break;
            budget += value[ready.poll()];                                 // take the best unlocked item
        }
        return budget;
    }
}

Complexity

Variations

• Streaming median: pure insert + query. Example: Find Median from Data Stream.
• Windowed median: insert, delete the outgoing element, rebalance, query. Example: Sliding Window Median.
• Unlock-then-pick greedy: one structure releases candidates as a threshold grows, a max-heap chooses among them. Example: IPO.
• Percentile, not median: keep sizes in a ratio such as 9:1 so the low top is the 90th percentile.
• TreeMap / multiset alternative: two TreeMap<value,count> halves give O(log n) deletion without lazy bookkeeping; handy in Java when duplicates are allowed.

Common mistakes

• Forgetting that new PriorityQueue<>() is a min-heap; the low half needs Collections.reverseOrder().
• Rebalancing only on size and not on order, so a value larger than high.peek() ends up in low. Routing every insert through the other heap prevents this.
• With lazy deletion, reading a heap top without first purging stale entries, or comparing real sizes instead of logical sizes.
• Using the comparator (a, b) -> b - a, which overflows for large negative and positive values; use Integer.compare.
• In IPO-style problems, re-scanning all projects every round (O(n·k)) instead of sorting by cost once and advancing a pointer.

All practice problems

3 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.