Find Median from Data Stream

Numbers arrive one at a time. After each one, report the median of every number seen so far.

Example

Stream: 5, 15, 1, 3 Medians after each insertion: 5.0, 10.0, 5.0, 4.0

Approach

This is the canonical two-heaps problem. Keep a max-heap (small) holding the lower half of numbers seen and a min-heap (large) holding the upper half, kept balanced so their sizes never differ by more than 1. The median is then either the top of whichever heap has one more element, or the average of both tops when they're equal in size. Every insertion is O(log n) — no re-sorting the whole stream on every new number.

Walkthrough

1def add_num(self, n):
2    heapq.heappush(self.small, -n)
3    heapq.heappush(self.large, -heapq.heappop(self.small))
4    if len(self.large) > len(self.small):
5        heapq.heappush(self.small, -heapq.heappop(self.large))

The naive alternative — keep one sorted array and insert each new number into its correct position — costs O(n) per insertion because the elements after it all have to shift. The two-heap approach never sorts anything; it just maintains the heap-order invariant, which costs O(log n) per insertion no matter how large the stream gets. Drag the scrubber above to see the gap widen as n grows.

Input format

Line 1: the stream of numbers, in arrival order, space-separated

Print the median after each insertion, formatted to 1 decimal place, space-separated.