The idea: split the numbers into two halves
Numbers arrive one at a time and you want the median after each one. Sorting everything again each time is slow. Instead, keep the numbers in two halves. The smaller half goes in a max-heap (called low), so its root is the largest small number. The larger half goes in a min-heap (called high), so its root is the smallest large number. The two roots sit right next to the middle.
The canvas shows both heaps as trees with their arrays, the stream at the top, and every number seen so far in sorted order: blue keys are in low, green keys are in high.
Two rules, and where the median is
- Order: every key in low is ≤ every key in high.
- Balance: low has the same number of keys as high, or one more.
With both rules, the median needs no search. An odd count means low holds the middle number, so the median is the top of low. An even count means the two middle numbers are the two roots, so the median is (top of low + top of high) / 2. Either way it costs O(1).
Adding one number
- Pick the half. If low is empty or x ≤ top of low, x goes to low; otherwise to high. One compare keeps the order rule.
- Push. Write x into the next free slot and sift it up: swap with the parent while it beats it (larger in low, smaller in high).
- Rebalance. If low now has 2 more keys than high, or high has more than low, pop the root of the bigger heap (its last key moves to the root and sifts down) and push it into the other heap.
- Read the median from the roots.
Moving a root across is safe: the largest key of low is still ≤ everything in high, and the smallest key of high is still ≥ everything in low. Each step is one heap operation, so an add costs O(log n): at most one push and one pop-and-push.
What the demos show
| demo | stream | medians after each number | rebalances |
|---|---|---|---|
| mixed stream | 5 15 1 3 8 7 9 10 6 11 4 | 5, 10, 5, 4, 5, 6, 7, 7.5, 7, 7.5, 7 | 3 |
| ascending stream | 11 22 33 … 88 | 11, 16.5, 22, … 49.5 | 3 |
| descending stream | 88 77 66 … 11 | 88, 82.5, 77, … 49.5 | 4 |
| duplicates | 5 5 5 3 5 7 5 5 | always 5 | 3 |
| outliers | 10 12 11 95 9 13 90 14 99 | 10, 11, 11, 11.5, 11, 11.5, 12, 12.5, 13 | 3 |
A sorted stream is the hardest case for balance. In the ascending stream every new number is larger than top of low, so it lands in high, and every second add must move high's root back to low (Demo: ascending stream). The descending stream is the mirror image. It still costs only O(log n) per add.
Duplicates are fine: a tie with top of low goes to low, and the order rule uses ≤, so equal keys may sit on both sides of the cut (Demo: duplicates).
The median is robust: in Demo: outliers move the mean, not the median, the numbers 95, 90 and 99 pull the mean up to 39.2, while the median only creeps from 10 to 13. See Mean vs Median vs Mode.
Compared with other ways
| method | per new number | median query |
|---|---|---|
| sort everything again | O(n log n) | O(1) |
| sorted array, insert in place | O(n) (shift) | O(1) |
| unsorted list + quickselect | O(1) | O(n) average |
| two heaps | O(log n) | O(1) |
| balanced BST with subtree sizes | O(log n) | O(log n) |
The heaps are plain array heaps, as on Heaps and Priority Queues; a max-heap is just a min-heap with the compare flipped. See also Heap Sort.
What the page leaves out
The page holds at most 25 numbers from 1 to 99. It leaves out the sliding-window median (numbers also leave, which needs delete by key, often done with lazy deletion or two balanced trees), other quantiles such as the 90th percentile (the same idea with the cut placed elsewhere), approximate quantile sketches for huge streams (t-digest, GK), and the order-statistic tree that answers any rank query.
See where this page fits on the Heap-like Data Structures mind map.