Streaming Median Tracker

Design a data structure that ingests integers one at a time from a stream and can report the median of every integer inserted so far at any moment.

The median of a collection of numbers is the middle value once the numbers are arranged in non-decreasing order:

• If the collection has an odd number of elements, the median is the single middle element.
• If the collection has an even number of elements, the median is the average of the two middle elements.

Implement a class MedianTracker with the following operations:

• MedianTracker() — initialize an empty tracker.
• add(num) — insert the integer num into the structure. Duplicates and negative values are allowed.
• median() — return the median of all integers inserted so far as a floating-point number. This method is only invoked after at least one call to add.

Example

MedianTracker t
t.add(1) // multiset = [1]
t.median() // returns 1.0
t.add(3) // multiset = [1, 3]
t.median() // returns 2.0 (average of the two middle values 1 and 3)
t.add(2) // multiset = [1, 2, 3]
t.median() // returns 2.0 (single middle value)
t.add(10) // multiset = [1, 2, 3, 10]
t.median() // returns 2.5 (average of 2 and 3)

Constraints

• Values passed to add are 32-bit signed integers; they may be negative and may repeat.
• add can be called up to $10^5$ times, interleaved arbitrarily with median calls. A solution that re-sorts the data on every median call (overall $O(n^2 \log n)$) is too slow — aim for roughly $O(\log n)$ per add and $O(1)$ per median.
• median is never called before the first add.
• The returned median must be exact: when the count is even, return the true average of the two middle elements (which may be a non-integer such as 2.5).

Required Output

Each call to median() returns a single floating-point number equal to the median of all integers inserted up to that point.