题解 | #数据流中的中位数#

import java.util.*;


public class Solution {
    int count = 0;
    Queue<Integer> min_heap = new PriorityQueue<>();
    Queue<Integer> max_heap = new PriorityQueue<>(Collections.reverseOrder());

    public void Insert(Integer num) {
        count++;
        if(!min_heap.isEmpty() && num > min_heap.peek()){
            //判断 是否加入的数字比小根堆里面最小的数字大 如果大则替换 
            max_heap.add(min_heap.poll());
            min_heap.add(num);
        }else{
		  	//否则直接加入大根堆
            max_heap.add(num);
        }
        
        if(max_heap.size() - min_heap.size() >1){
		  //使大小根堆保持数量不大于1 且只能大根堆比小根堆多元素
            min_heap.add(max_heap.poll());
        }

    }

    public Double GetMedian() {
        double result;
        if(count % 2 ==0 ){
		  //如果有数字个数为偶数 则取其平均数
            result = (min_heap.peek()+max_heap.peek())/2.0;
        }else{
		  //直接取大根堆堆顶的元素
            result = max_heap.peek();
        }
        return result;
    }


}