Find Median from Data Stream

Implement a median data structure for a stream of integers. addNum x: add integer x. findMedian: return the median of all values seen so far. For an odd count, it is the middle value; for an even count, it is the average of the two middle values. Target complexities: O(log n) for addNum and O(1) for findMedian. Input The first line contains q. Each of the following q lines is one of: addNum x findMedian Print one result for every findMedian. Print integral medians as integers and non-integral medians with one decimal place. Example Input: 5 addNum 1 addNum 2 findMedian addNum 3 findMedian Output: 1.5 2 Example Input 5 addNum 1 addNum 2 findMedian addNum 3 findMedian Output 1.5 2