Find Median From a Data Stream

Problem Design a data structure that supports two operations over a stream of integers: addNum(x) to ingest a value, and findMedian() to return the median of all values seen so far.

Input / Output

• Input: interleaved addNum(x) and findMedian() calls.
• Output: findMedian returns the current median (the average of the two middle values when the count is even).

Constraints

• Up to 5 × 10^4 calls; addNum should be better than re-sorting each time.

Example

• addNum(1), addNum(2) → findMedian() = 1.5; addNum(3) → findMedian() = 2.