解题思路

定义一个小根堆和大根堆，插入元素只插入到大根堆中，我们让大根堆的堆顶小于小根堆的堆顶同时大根堆的个数保持比小根堆多一个或者一样大，如果不满足条件一，我们就交换两个堆的堆顶元素，不满足条件二，我们就把大根堆元素出堆放到小根堆中。

class Solution {

    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b)->(b-a));
    public void insert(Integer num) {
        maxHeap.offer(num);
        if(!minHeap.isEmpty() && maxHeap.peek() > minHeap.peek()){
            int max = maxHeap.poll(), min = minHeap.poll();
            minHeap.offer(max);
            maxHeap.offer(min);
        }
        if(maxHeap.size() > minHeap.size()+1){
            minHeap.offer(maxHeap.poll());
        }
    }

    public Double getMedian() {
        if((minHeap.size() + maxHeap.size() & 1) == 1){
            return maxHeap.peek()*1.0;
        }else{
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }

}