利用PriorityQueue求动态数据流中的中位数

使用大小顶堆来进行插入时排序。

需要求的是中位数，如果我将 1 2 3 4 5 6 7 8定为最终的数据流
此时的中位数是4+5求均值。为什么是4，为什么是5
利用队列我们就可以看得很清楚，4是前半部分最大的值，肯定是维系在大顶堆
而5是后半部分的最小值，肯定是维系在小顶堆。
问题就好理解了：
使用小顶堆存大数据，使用大顶堆存小数据。这样堆顶一取出就是中位数了。

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>(){
        public int compare(Integer o1, Integer o2){
            return o2.compareTo(o1);
        }
    });

    public void Insert(Integer num) {
        //数量++
        cnt++;
        if((cnt & 1) == 1){    //数据流为奇数
            if(!low.isEmpty() && num > low.peek()){    
                low.offer(num);
                //会吐出最小的数
                num = low.poll();
            }

            high.offer(num);
        }else{
            if(!high.isEmpty() && num < high.peek()){
                high.offer(num);
                //大顶堆最小的数，在小顶堆就是最大的数
                num = high.poll();
            }
            low.offer(num);
        }


    }

    public Double GetMedian() {
        double res = 0;
        if((cnt & 1) == 1){
            res = high.peek();
        }else{
            res = (high.peek() +low.peek()) / 2.0;
        }
        return res;
    }


}

其实除此之外还有其他几个思路： * 使用无序数组存储，在得到中位数前对数组进行排序。（这是最容易想到的）

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    ArrayList<Integer> array = new ArrayList<>();
    public void Insert(Integer num) {
        array.add(num);
    }

    public Double GetMedian() {
        Collections.sort(array);
        int index = array.size()/2;
        if(array.size()%2 != 0){  //奇数直接取
            return (double)array.get(index);
        }
        return ((double)(array.get(index-1))+(double)array.get(index))/2;//偶数平均值
    }
}

• 插入时排序，不利用堆，而是利用二分法。

import java.util.LinkedList;
import java.util.List;
public class Solution {
    private List<Integer> list = new LinkedList();

    public void Insert(Integer num) {
        if(list.size()==0){
            list.add(num);
            return;
        }
        int first = 0;
        int last = list.size()-1;
        int mid = 0;
        while(first <= last){
            mid = (first+last)/2;
            if(list.get(mid)>num)
                last = mid-1;
            else
                first = mid+1;
        }
        list.add(first,num);
        return;
    }

    public Double GetMedian() {
        int index = list.size();
        if(index%2==1){
            return (double)list.get(index/2);
        }
       return ((double)(list.get(index/2-1))+(double)list.get(index/2))/2;
    }
}