Two Heaps Pattern

Why Two Heaps Create a Stable Split

Some interview problems are really asking you to maintain a moving border between a smaller half and a larger half of the data. The median is the cleanest example: everything on the left side should be less than or equal to everything on the right side, and the answer depends only on the elements closest to that border. Two heaps are perfect for this because a max-heap exposes the largest value on the left, while a min-heap exposes the smallest value on the right.

The pattern works by preserving two invariants. First, every value in the left heap must be less than or equal to every value in the right heap. Second, the heaps must stay balanced so the border sits in the right place. Once those invariants hold, the answer is immediate. If one heap has an extra element, its top is the median. If the heaps are equal, the two tops average together.

This idea generalizes beyond medians. Sometimes one heap stores candidates you can now afford and the other stores candidates you might afford later. Sometimes one heap tracks the best values on the left side of a cut while another protects the right side. The deeper pattern is partition maintenance: the frontier between two regions matters more than the full sorted order.

Running Median Example

Insert the stream 5, 2, 10, 4 one value at a time. Start with 5 in the left max-heap. The heaps are left = [5], right = [], so the median is 5. Insert 2 next. Because 2 belongs on the smaller side, push it to the left heap, which now has two elements. Rebalance by moving the largest left value, 5, into the right heap. Now left = [2], right = [5], and the median is 3.5.

Insert 10. It is larger than the left-side maximum, so it belongs in the right heap. The right heap now has two elements while the left has one, so the median is the right top, 5. Insert 4 next. After the correct push and rebalance, the heaps represent [2,4] and [5,10], so the median is 4.5. We never sort the entire stream; we only repair the frontier around the answer.

Go Implementation

In Go, container/heap only implements a min-heap, so a common trick for the left side is storing negated values. That lets one heap type represent both halves while keeping the public median logic easy to read.

Some variants, especially those with deletions, also need explicit top pruning or order repairs. But the mental model does not change: if a frontier element belongs on the other side of the split, move it; if one side owns too many elements, rebalance size.

Other Two-Heap Variants

IPO uses one min-heap ordered by required capital and one max-heap ordered by profit. As your current capital grows, projects migrate from “unaffordable” to “available,” and the max-heap picks the best currently legal profit. Sliding Window Median uses the same partition as the stream version, but adds lazy deletion because values eventually leave the window. Prefix/suffix optimization problems often use a max-heap on the left and a min-heap on the right to evaluate every possible cut.

A good interview explanation names the split in words. If you cannot say what each heap represents, you probably do not yet have the right pattern. “Smaller half versus larger half,” or “available versus unavailable” are strong descriptions because they explain both the data structures and the rebalancing rules.

Practice Problems

Quiz