（java版剑指offer）JZ41 数据流中的中位数

//方法：大顶堆和小顶堆法
//时间复杂度：nlogn
//空间复杂度：n
import java.util.*;
public class Solution {
    //解决方法：堆
    //新建大顶堆和小顶堆
    
    private int cnt = 0;    //静态计数
    
    // 默认维护小顶堆，放后半段的值
    private PriorityQueue<Integer> low = new PriorityQueue<>();    //小顶堆,降序排列
    //大顶堆，放前半段的值
    private PriorityQueue<Integer> high = new PriorityQueue<>(new Comparator<Integer>(){
        @Override
        public int compare(Integer o1, Integer o2){
            return o2.compareTo(o1);
        }
    });    //重写compare方法，实现大顶堆，升序排列

    public void Insert(Integer num) {
        //动态计数
        //奇数放在大顶堆，前提是新插入的数要比小顶堆上的数小，否则要放入小顶堆中，
            //最后将重排后小顶堆上的数吐出放入大顶堆中
        //偶数放在小顶堆，前提是新插入的数要比大顶堆大，否则要放入大顶堆中
            //等大顶堆重排后，将大顶堆上的数吐出放入小顶堆中
        
        cnt++;    //插入值，自增
        //cnt为奇数，新插入的值要放入大顶堆中
        if((cnt & 1) == 1){
            //判断小顶堆不为空，且新插入的值是否比小顶堆上的值小,那么将num先放入小顶堆中重排序
            if(!low.isEmpty() && num > low.peek()){
                low.offer(num);    //小顶堆重建
                num = low.poll();    //弹出根节点的值，重建小顶堆
            }
            high.offer(num);
        }
        
        //cnt为偶数，新插入的值要放在小顶堆中
        if((cnt & 1) == 0){
            //判断大顶堆为空，且新插入的值小于大顶堆的根节点的值
            if(!high.isEmpty() && num < high.peek()){
                high.offer(num);
                num = high.poll();
            }
            low.offer(num);
        }
    }

    public Double GetMedian() {
        //定义双精度变量存放平均值
        double aver = 0;
        //cnt为奇数，取大顶堆的根节点的值
        if((cnt & 1) == 1){
            aver = high.peek();
        }
        //cnt为偶数，取大顶堆和小顶堆的根节点的平均值
        if((cnt & 1) == 0){
            aver = (high.peek() + low.peek())/2.0;
        }
        return aver;
    }


}