Running median with two heaps

Question

Prices arrive one at a time. After each arrival, report the median of everything seen so far, a robust mid-price estimate that outliers can't drag around.

add(5)  -> median 5
add(3)  -> median 4.0      # of {3, 5}
add(8)  -> median 5        # of {3, 5, 8}
add(9)  -> median 6.5      # of {3, 5, 8, 9}

Support add in $O(\log n)$ and median in $O(1)$ . Re-sorting per tick is $O(n \log n)$ ; keeping a sorted list with insertion is $O(n)$ per add because of element shifting.

Accepted Answer

Keep two heaps meeting at the median: a max-heap lo holding the smaller half and a min-heap hi holding the larger half, balanced so that len(lo) is either equal to or exactly one more than len(hi). The median is then the top of lo (odd count) or the average of the two tops (even count). Python's heapq is min-only, so implement the max-heap by storing negated values. The push-then-rebalance dance below guarantees both the ordering invariant (every element of lo is at most every element of hi) and the size invariant, regardless of where the new value belongs: Tracing the example: after 5, 3 the…

Running median with two heaps

Your answer

More Coding questions