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

import java.util.Comparator;
import java.util.PriorityQueue;


public class Solution {
    // 思路：用最大顶堆和最小顶堆
    // 最大堆存储较小的值，顶部是最大值；最小堆存放较大的值，顶部是最小值
    // 奇数，取最大堆顶，偶数，取俩堆顶平均值。最大堆顶个数要么等于最小堆顶，要么比它多一个

    // 最大堆里面放较小的值
    PriorityQueue<Integer> pqMax = new PriorityQueue<>(new Comparator<Integer>(){
        @Override
        public int compare(Integer a,Integer b){
            return b.compareTo(a);
        }
    });

    // 最小堆里面放较大的值
    PriorityQueue<Integer> pqMin = new PriorityQueue<>();

    public void Insert(Integer num) {
        // 先把数字加入最大堆
        pqMax.offer(num);
        // 加入一个数字进最大堆，就从最大堆里面拿一个最大的数字放进最小堆
        pqMin.offer(pqMax.poll());
        if(pqMax.size() < pqMin.size()){
            //这样能保证pqMax的个数是大于等于pqMin的
            pqMax.offer(pqMin.poll());
        }

    }

    public Double GetMedian() {
        if(pqMax.size() == pqMin.size()){
            return (double)(pqMax.peek()+pqMin.peek()) / 2;
        }else{
            return (double)pqMax.peek() ;
        }
    }


}

思路：用两个堆来完成中位数的计算。需要捋清楚的是，最大堆装较小的数据，最小堆装较大的数据。

由于我的定位是，偶数，取两个堆顶的平均值，奇数，只取最大堆的堆顶。也就是说，最大堆的个数是大于等于最小堆的。

赋值的时候，先把数据装进最小堆，然后比较最大堆与最小堆的个数，当最大堆小于最小堆的时候，就把数据转到最大堆。

一开始把数据装进最小堆，然后从最小堆匀苏剧给最大堆的时候，要注意，为了保证数据的较大部分在最小堆，较小部分在最大堆，数据是经历了两次清洗的，一开始数据进入最大堆然后进入最小堆，然后从最小堆匀数据给最大堆。

求中位数的时候也要注意，这只是求值，不要改变堆里面的数据，我一开始用了pop结果出错，应该用peek，只是取值，不改变堆里面的数据。然后注意强制转换问题。