Live Median Tracker

Write a class MedianTracker that receives integers one at a time and can report the median of everything received so far.

• MedianTracker() starts empty.
• add(x) records the integer x.
• median() returns the median as a float: for an odd count the middle value, for an even count the mean of the two middle values. It is only called after at least one add.

Examples

Input:  ops  = ["MedianTracker", "add", "add", "median", "add", "median", "add", "median"]
        args = [[], [5], [15], [], [1], [], [3], []]
Output: [None, None, None, 10.0, None, 5.0, None, 4.0]
Explanation: {5, 15} -> 10.0; {1, 5, 15} -> 5.0; {1, 3, 5, 15} -> (3 + 5) / 2 = 4.0.

Constraints

• Up to 10**5 calls, values in [-10**9, 10**9], duplicates allowed
• Target complexity: add in O(log n), median in O(1).

Goals

• Split a stream into a lower half and an upper half with two heaps
• Rebalance so the halves differ in size by at most one
• Read the median from the heap tops without sorting