Practice: Median of a Stream
Two heaps.
Numbers arrive one at a time, and after each one, you need the median, the middle value. Sorting every time is far too slow. The clever answer uses two heaps.

- Numbers keep arriving
- Find the median each time
- Two heaps
Two halves
Keep the smaller half of the numbers in a max heap, and the larger half in a min heap. Keep the halves balanced, so they differ in size by at most one. Then the median is right at the top of the heaps. Either the top of the bigger one, or the average of both tops.
Median finder
Python only has min heaps, so we store the low half as negative numbers. Each new number goes into the low half, then its largest moves to the high half. If the high half gets bigger, we move one back. Run it. The median after each number.
import heapq
low, high = [], []
def add(x):
heapq.heappush(low, -x)
heapq.heappush(high, -heapq.heappop(low))
if len(high) > len(low):
heapq.heappush(low, -heapq.heappop(high))
def median():
if len(low) > len(high):
return -low[0]
return (-low[0] + high[0]) / 2
for x in [5, 15, 1, 3, 8]:
add(x)
print(x, "->", median())5 -> 5 15 -> 10.0 1 -> 5 3 -> 4.0 8 -> 5
Summary
Keep the low half in a max heap and the high half in a min heap. The median sits at the tops, and each new number costs O of log N. Next, the biggest number in every window.
Key takeaways- Max heap for the low half
- Min heap for the high half
- Median at the tops