获取中间数 剑指Offer 62

优先队列PriorityQueue说白了就是一个最小堆，其中存储元素并不是按照顺序存储，但是检索是按照顺序的，remove操作总是删除最小的元素。
父接口接口有Queue 和Collection

问题:
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

LinkedList 解决方案

public class Solution {
    LinkedList<Integer> list = new LinkedList<>();

    public void Insert(Integer num) {
        int index = 0;
        for(Integer i : list){
            if(num < i) break;
            index ++;
        }// 找到要插入数据的位置，这里使用forEach提高效率
        if(list.size() == index) list.add(num);
        else list.add(index , num);
    }

    public Double GetMedian() {
        int avg = list.size()/2; // 获取中位数下标
        if(list.size() % 2 != 0){
            return (double) list.get(avg);
        } else{
            return (list.get(avg) + list.get(avg-1))/2.0;
        }
    }
}

PriorityQueue 解决方案

使用最大堆和最小堆。把堆看做一个漏斗状的东西，两个堆刚好就是一个沙漏，两个堆顶正好是要找的中位数。
要保证堆顶是中位数：

1. 对于奇数个数，添加到MinHeap中，然后将MinHeap中最小值添加到MaxHeap中
2. 对于偶数个数，添加到MaxHeap中，然后将MaxHeap中最大值添加到MinHeap中

    boolean is2n = true; // 堆中数字数量，0，偶数
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(1);
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(1, Comparator.reverseOrder());

    public void Insert(Integer num) {
        if (is2n) {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        }else{
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        }
        is2n = !is2n;
    }

    public Double GetMedian() {
        if (!is2n) return (double) minHeap.peek();
        else return (maxHeap.peek() + minHeap.peek()) / 2.0;
    }

效率对比

数据类型/插入数据量	1000	10000	100000
LinkedList	7	322	51959
PriorityQueue	3	11	46