Leetcode - Find Median from Data Stream

My code:

public class MedianFinder {
    PriorityQueue<Integer> big = new PriorityQueue<Integer>();
    PriorityQueue<Integer> small = new PriorityQueue<Integer>();
    // Adds a number into the data structure.
    public void addNum(int num) {
        big.offer(num);
        small.offer(-1 * big.poll());
        if (small.size() > big.size()) {
            big.offer(-1 * small.poll());
        }
    }

    // Returns the median of current data stream
    public double findMedian() {
        if (big.size() > small.size()) {
            return big.peek() * 1.0;
        }
        else {
            return (big.peek() - small.peek()) / 2.0;
        }
    }
};

// Your MedianFinder object will be instantiated and called as such:
// MedianFinder mf = new MedianFinder();
// mf.addNum(1);
// mf.findMedian();

this solution is so cool.
自己没能写出来，看了答案，理解了，再写，还是错。然后才终于理解了原答案中一些我觉得完全必要的步骤，其实完全是有必要的。

reference:
https://discuss.leetcode.com/topic/27521/short-simple-java-c-python-o-log-n-o-1

他其实就是维护两个堆，一个是 Min-heap, 一个是 max-heap

然后 min-heap 放整个数据流右半部分的数据，即，较大的数据那部分。
max-heap 放整个数据流左半部分的数据，即，较小的数据那部分。

然后， top of max-heap and top of min-heap 正好是中间的值。
如果个数是奇数，那就是 top of min-heap 是 median
如果个数是偶数，那就是 (top of min-heap + top of max-heap) / 2

然后他用了两个技巧来实现这么两个堆。
1.每次先往最小堆加入元素。
然后 Poll 出来，这时候poll 出来的一定是右半部分最小的数值。

？？ 但他也一定是左半部分最大的数值。把它押进左半部分。 ？？
如果此时左半部分个数大于了右半部分的，那么再把左半部分的最小大值，弹出来给右半部分

2. 正如上面打问号的部分，这个说法是错的。
   如果刚进来的值就是最小的，那么他就会被 big 弹出来，然后插入small, small 再把他里面最大的值弹出来给big
   所以这里其实有一个reheap 的过程。我一开始忽略掉了，所以有错。

为了实现 max-heap 的效果，small 都是插入负值，这样，优先级就会颠倒。也就是 map-heap 了。

Anyway, Good luck, Richardo! -- 09/15/2016