295.数据流的中位数

• 当大根堆和小根堆的size都是0时，元素默认进大根堆
• 1）num <= 大根堆的顶， num进大根堆，否则进小根堆
• 2）大根堆的size比小根堆大2，大根堆堆顶进小根堆
  • 小根堆的size比大根堆大2， 小根堆堆顶进大根堆

大根堆的堆顶和小根堆的堆顶就是中间的两个数

例子 5 3 6 4 2 1

 class MedianFinder {
        private PriorityQueue<Integer> maxh;
        private PriorityQueue<Integer> minh;
        public MedianFinder() {
            maxh = new PriorityQueue<>((o1, o2) -> o2 - o1);
            minh = new PriorityQueue<>((o1, o2) -> o1 - o2);
        }
        public void addNum(int num) {
            if (maxh.isEmpty()) {
                maxh.add(num);
            } else {
                if (maxh.peek() >= num) {
                    maxh.add(num);
                } else {
                    minh.add(num);
                }
            }
            balance();
        }
        public double findMedian() {
            if (maxh.size() == minh.size()) {
                return (double) (maxh.peek() + minh.peek()) / 2;
            } else {
                return maxh.size() > minh.size() ? maxh.peek() : minh.peek();
            }
        }
        private void balance() {
            if (maxh.size() == minh.size() + 2) {
                minh.add(maxh.poll());
            }
            if (maxh.size() == minh.size() - 2) {
                maxh.add(minh.poll());
            }
        }
    }