参考资料：左神算法课+《剑指offer》
295. Find Median from Data Stream
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.
For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Implement the MedianFinder class:
MedianFinder() initializes the MedianFinder object.
void addNum(int num) adds the integer num from the data stream to the data structure.
double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.
Example 1:
Input
[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]
Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0
观察到：小于中位数的数的个数 与 大于中位数的数的个数 相差 <=1 ； 如果对数组排序的话，小于中位数的数 总是 位于 中位数 左侧，大于中位数的数总是 位于中位数右侧。
思路：建立大根堆、小根堆，第一个数据来到后，先进大根堆；之后的数，与大根堆的堆顶比较，决定它进大根堆还是小根堆。具体地，如果新数小于大根堆堆顶，那么进大根堆；如果新数大于大根堆堆顶，那么进小根堆。然后，调整两个堆（balance()），使得二者size相差≤1，这样才能“暴露”出两个“预备中位数“（指大根堆、小根堆的堆顶），便于找出中位数。
《剑指offer》给出的思路与之类似，但是 在维护两个堆大小的调整上有些别扭（个人感觉），而 算法课 给出的代码更自然——先往大根堆里加，后来的数与大根堆堆顶比较，加入到相应的堆中后，用balance函数一起调整两个堆的size。
class MedianFinder{private PriorityQueue<Integer> minh;private PriorityQueue<Integer> maxh;public MedianFinder(){minh = new PriorityQueue<>((a,b)->a-b);maxh = new PriorityQueue<>((b,a)->b-a);}public void addNum(int num){if(maxh.isEmpty()){maxh.add(num);}else{if(maxh.peek()>=num){maxh.add(num);}else {minh.add(num);}}balance();}public void balance(){if(maxh.size()-minh.size()==2){minh.add(maxh.poll());}if(minh.size()-maxh.size()==2){maxh.add(minh.poll());}}public double findMedian(){if(((maxh.size()+minh.size())&1)==1){// oddreturn maxh.size()>minh.size()?maxh.peek():minh.peek();}else {return (double)(maxh.peek()+minh.peek())/2;}}}
