Find Median from Data Stream

Problem

Design a data structure that supports two operations on a stream of integers arriving one at a time: addNum(num) — add a number to the running data set — and findMedian() — return the median of all numbers added so far. Both must run efficiently, called repeatedly as the stream grows. (LeetCode 295.)

Examples

Constraints

up to 5·10⁴ calls total to addNum/findMedian.

Attempt it first

The naive approach — keep every number in a sorted structure and read the middle — either re-sorts on every insert (expensive) or maintains a sorted list with O(n) insertion (shifting elements). This module's whole point is that a SINGLE heap only ever gives you fast access to one end (the min or the max) of the data — but a median needs fast access to the middle. Before opening anything, think about how you could use TWO heaps together so that the median always sits at a boundary between them, accessible in O(1) — this is the module's centerpiece technique, worth genuinely struggling with before reading on.