Find Median from Data Stream

给一个数据流(数组表示), 写一个API, 返回每个时刻的median. 因为是中间数, 所以我们可以把数据流看成两段数组的和, 考虑一下如果输入是一个已经排序好的数组, 那么中间的那个数就是答案. 所以我们只需要知道中间的两个数是哪两个就好, 这里用的是一个min heap和一个max heap, 来tracking中间的两个数. 需要注意如何保持两个heap的平衡, 即当放入min heap后, 需要poll最小的数放到max的里. 当然 如果输入的数组连续都是同样的数, 我们还要通过判断max和min的大小, 来重新平衡两个heap.

class MedianFinder {
   private Queue<Integer> small = new PriorityQueue(1, new Comparator<Integer>() {
		   public int compare(Integer o1, Integer o2) {
			   return o2 - o1; 
		   };
   });
	   
   private Queue<Integer> large = new PriorityQueue();
    // Adds a number into the data structure.
    public void addNum(int num) {
        large.add(num); // add to min heap first
        small.add(large.poll()); // poll the smallest to small
        if (large.size() < small.size()) // if we pulled same number 
            large.add(small.poll());// poll back...
    }

    // Returns the median of current data stream
    public double findMedian() {
        return large.size() > small.size() // if the length is odd
               ? large.peek()
               : (large.peek() + small.peek()) / 2.0;
    }
}