Find Median from Data Stream

HardTwo heapsTime O(log n) add, O(1) medianSpace O(n)

Find Median from Data Stream is a hard Heap / Priority Queue problem from the Blind 75. The key pattern is two heaps, and a good solution runs in O(log n) add, O(1) median time.

Problem

Process add and median operations; return each median as a number in operation order.

Examples

Example 1

Input

[["add",4],["add",9],["median"],["add",1],["median"]]

Output

[6.5,4]

Example 2

Input

[["add",1],["median"],["add",2],["median"],["add",3],["median"]]

Output

[1,1.5,2]

Example 3

Input

[["add",5],["add",5],["median"]]

Output

[5]

Approach

Keep the smaller half in a max-heap and the larger half in a min-heap, with sizes differing by at most one. The median comes from the heap tops.

Pattern	Two heaps
Time	O(log n) add, O(1) median
Space	O(n)

Watch out for

With an even count the median is the average of the two middle values.