算法思想

维护一个大根堆和一个小根堆 ==> 大根堆存储小的数，小根堆存储大的数

这样的话,大根堆的堆顶和小根堆的堆顶就是中间的内两位数
如果是奇数的话，直接返回大根堆的堆顶就可以了
如果是偶数的话，返回两个堆顶 / 2.0就可以了

维护大根堆和小根堆

• 每次一有新的数，先插入到大根堆中去
• 因为大根堆存储小的数，所以如果大根堆的堆顶变大了，大于小根堆的堆顶，那么就交换位置
• 因为是把区间分成了两半，所以大根堆和小根堆的大小应该不超过1，超过了就向小根堆转移

java代码

class Solution {

    static Queue<Integer> min_heap = new PriorityQueue<>();   //小根堆存储大的数，大根堆存储小的数
    static Queue<Integer> max_heap = new PriorityQueue<>((a,b) -> (b - a));
    public void insert(Integer num) {
        max_heap.offer(num);
        while(min_heap.size() != 0 && max_heap.peek() > min_heap.peek())
        {
            int a = max_heap.poll(), b = min_heap.poll();
            max_heap.offer(b);
            min_heap.offer(a);
        }
        if(max_heap.size() > min_heap.size() + 1) min_heap.offer(max_heap.poll());
    }

    public Double getMedian() {
        if((min_heap.size() + max_heap.size()) % 2 == 1) return max_heap.peek() - 0.0;
        return (min_heap.peek() + max_heap.peek()) / 2.0;        //返回double
    }

}