Two heaps (running median)

49 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Numbers arrive one at a time: 5, 15, 1, 3. After each one you must report the median, the middle value when sorted (or the average of the two middle values when the count is even). By hand you keep a sorted list and look at the middle: [5] → 5; [5, 15] → 10; [1, 5, 15] → 5; [1, 3, 5, 15] → 4. Keeping a list sorted costs a shift of about half the list per arrival, so after a million numbers each new number costs hundreds of thousands of moves.

Notice what the median actually needs: the largest value of the lower half and the smallest value of the upper half. Nothing else in either half is ever read. So we do not need the halves sorted, we only need each half to expose one end.

Build the structure, one piece at a time

Piece one: a max-heap called low, which can always show its largest element at once. It will hold the smaller half of the numbers.

Piece two: a min-heap called high, which always shows its smallest element. It holds the larger half. The two visible elements are the two middle values.

Piece three: the rules that keep the halves honest. Insert a newcomer into low if it is at most low's top, else into high. Then rebalance: if one heap has two more elements than the other, move its top to the other heap. Keep low allowed to be larger by one, so that with an odd count the median is simply low's top.

After the move: low = {3, 1} with top 3, high = {5, 15} with top 5. The medians match the by-hand list.

Why it is correct

Two invariants. First, every element in low is at most every element in high. Inserting keeps it: a newcomer goes to low only if it is ≤ low's top, which is low's maximum, so it is ≤ everything in high; otherwise it is > low's maximum, so it belongs above all of low. Moving a top across keeps it too, because the moved element is at the boundary. Second, the sizes differ by at most one, which the rebalance step restores immediately.

median = top(low) if |low| = |high| + 1, else (top(low) + top(high)) / 2

With both invariants, low is exactly the smaller half (by count) and high the larger half, so the two tops are exactly the middle values.

Why it is fast

Each arrival does one heap push, at most one pop and one push for rebalancing, each O(log n). Reading the median is O(1), two lookups. Compared with the sorted list, O(n) per arrival, that is 20 steps instead of 500,000 for a million numbers. Memory is all n numbers, as it must be, since any of them can become the median later.

How to recognise it in an interview

"Median of a stream", "running median", or any task that needs the boundary between the lower and upper parts of a growing set, including "sliding window median" (with lazy deletion for elements leaving the window). Say: "I will keep the lower half in a max-heap and the upper half in a min-heap, balanced to within one element; the tops are the median." Find Median from Data Stream is this exactly. IPO uses the same two-pool idea differently: projects you can afford move from a min-heap by cost into a max-heap by profit.

02The idea in one line

A max-heap for the lower half, a min-heap for the upper; keep sizes balanced.

Reach for it when: Median from data stream, sliding window median, IPO-style two-pool problems.

Cost: O(log n) per insert.

03The walk-through, step by step

The video works one example: Median stream: 5, 15, 1, 3. These are its captions in order, so you can follow without the video or check a step you missed.

1. Split the numbers: low half in a max-heap, high half in a min-heap
2. 5 goes to low (≤ low's top)
3. Median = low top = 5
4. 15 goes to high (> low's top)
5. Median = average of both tops = 10
6. 1 goes to low (≤ low's top)
7. Median = low top = 5
8. 3 goes to low (≤ low's top)
9. low is 2 bigger: move its top to high to rebalance
10. Median = average of both tops = 4
11. 8 goes to high (> low's top)
12. high is bigger: move its top to low to rebalance
13. Median = low top = 5
14. Every element in low ≤ every element in high; sizes differ by at most 1
15. Each insert is one or two heap ops: O(log n)

04Asked at Google

4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Heap: Top-k with a size-k heap, K-way merge, Greedy scheduling with a heap, Lazy deletion heap, Pop-k-then-rebuild (frequency greedy).