# 0295. Find Median from Data Stream
###### tags: `Leetcode` `Priority Queue` `Hard`
Link: https://leetcode.com/problems/find-median-from-data-stream/
## 思路 $O(logN)$ add, $O(1)$ findMedian
参考[这里](https://leetcode.com/problems/find-median-from-data-stream/discuss/74047/JavaPython-two-heap-solution-O(log-n)-add-O(1)-find)
分成两个heap smaller和larger smaller的size大于等于larger的size, which is n/2
smaller heap是max heap把最大值放在最上面
larger heap是min heap把最小值放在最上面
## Code

class MedianFinder {
    Queue<Integer> smaller;
    Queue<Integer> larger;
    boolean even;
    public MedianFinder() {
        smaller = new PriorityQueue<>(Collections.reverseOrder());
        larger = new PriorityQueue<>();
        even = true;
    }
    
    public void addNum(int num) {
        if(even){
            larger.offer(num);
            smaller.offer(larger.poll());
        }
        else{
            smaller.offer(num);
            larger.offer(smaller.poll());
        }
        even = !even;
    }
    
    public double findMedian() {
        if(even) return (double)(smaller.peek()+larger.peek())/2;
        else return smaller.peek();
    }
}