295. Find Median from Data Stream

For example: 1 2 -3 4 => the ans: -3 1 2 4 => Median is 1.5

separate into two heaps (minheap), large and small

概念是分成兩群, 小的群取最大的, 大的群取最小的,

統一都用min heap, 所以加到 small 時, 都會用負的加入,

透過-large.poll(), 把小的加到small

large.add((long)num);
small.add(-large.poll());

if (large.size() < small.size()) {

用來維持兩邊 heap 數量平衡,

當small 太多時, 利用large.add(-small.poll()); 加回去large

=> -small.poll() 此時雖然是其poll min, 但其實會是把"最大"的加回 large (因為之前都是把負過的值加到small), 因為之前負過, 所以要在負回來

當奇數個數時, large 會比較多個數,

偶數個數時, large 和small　的個數會一樣

        if (large.size() < small.size()) {
            large.add(-small.poll());
        }

奇數case

For example: 1 2 -3

the ans: -3 1 2

when 1 enter, large.add(1)

small: 
large: 1

small.add(-large.poll()) => small.add(-1)

small: -1
large:

=> small size > large size (奇數時, 維持 large 比較多個數

=> -small.poll() -(-1) add to large

small: 
large: 1

when 2 enter, large.add(2)

small: 
large: 1, 2

small.add(-large.poll()) => small.add(-1)

small: -1

large: 2

when -3 enter, large.add(-3)

small: -1

large: 2, -3

small.add(-large.poll()) => small.add(3)

small: -1, 3

large: 2

=> small size > large size

=> -small.poll() -(-1) add to large

small: 3 

large: 2, 1 => large 取最小 (min heap peek()

奇數時, 就取large 的最小即可

偶數case

For example: 1 2 -3 4

the ans: -3 1 2 4

small: 3, -1 => small 取最小 (min heap peek()

large: 2, 4 => large 取最小 (min heap peek()

偶數時, small large 兩邊數量相等,

中位數: large 取最小, small 取最小(其實代表實際上最大, 因為加入時都作過負號),

相加除2 ⇒ 2 -(-1) /2 = 1.5 (因為small 放入時都是放負的, 所以要用 - 去加)

time: O(logn)

space: O(n)

class MedianFinder {
    
    private PriorityQueue<Long> large;
    private PriorityQueue<Long> small;

    /** initialize your data structure here. */
    public MedianFinder() {
        large = new PriorityQueue<>();
        small = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        large.add((long)num);
        small.add(-large.poll());
        if (large.size() < small.size()) {
            large.add(-small.poll());
        }
    }
    
    public double findMedian() {
        // notice divide by 2.0, or the presision lost
        return (large.size() > small.size()) ? large.peek() : (large.peek() - small.peek())/2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */