Find Median from Data Stream

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples: 
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.
For example:

add(1)
add(2)
findMedian() -> 1.5
add(3) 
findMedian() -> 2

Analysis

Example: add [1,2,3,4,5,6,7] to MedianFinder

注意：

1. priorityqueue要设为存储long or double,否则最后无法输出double
2. 最后除以2.0不是2

Code

class MedianFinder {

    PriorityQueue<Long> large = new PriorityQueue<>(); //keep the larger half of nums
    PriorityQueue<Long> small = new PriorityQueue<>(); //keep the smaller half of nums

    // Adds a number into the data structure.
    public void addNum(int num) {
        large.add((long) num);
        //small中放负数保证poll的时候可以取出绝对值大的数
        //新进来的数永远先放到large里，然后再从large里把相对小的数转移到small中去
        small.add(-large.poll());
        //永远保持large的size要大于等于small
        //如果小了，就把small中最小(实际是最大因为是负数)的数拿出来放到large中，因为large放的是大的一半
        if (large.size() < small.size()) large.add(-small.poll());
    }

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

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

Reference

Leetcode