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

import java.util.* ;
public class Solution {
    //小-》大
    PriorityQueue<Integer> p1 = new PriorityQueue<>() ;
    //大-》小
    PriorityQueue<Integer> p2 = new PriorityQueue<>(new Comparator<Integer>(){
        public int compare(Integer i1 , Integer i2) {
            return i2 - i1 ;
        }
    }) ;
    public void Insert(Integer num) {
        //先进小顶堆再进大顶堆保证了大顶堆的最小值都大于小顶堆的最大值
        p1.offer(num) ;
        p2.offer(p1.poll()) ;
        if(p2.size() - p1.size() > 1) {
            p1.offer(p2.poll()) ;
        }
    }

    public Double GetMedian() {
        if(p2.size() > p1.size()) {
            return p2.peek()*1.0 ;
        } else {
            return (0.0 + p1.peek() + p2.peek())/2 ;
        }
    }


}