【剑指offer】数据流中的中位数

题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
1、思路分析
利用优先队列小顶堆和大顶堆的特点，小顶堆的堆顶元素是最小元素，大顶堆的堆顶元素是最大元素，我们只要保证小顶堆中的元素均大于等于大顶堆中的元素，这样其实就形成了一种寻找中位数的结构，即我们找中位数的时候只需关心两个堆的堆顶即可。
2、代码

import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
    // 小顶堆，用该堆记录位于中位数后面的部分
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    // 大顶堆，用该堆记录位于中位数前面的部分
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(15,new Comparator<Integer>() {
        @Override
        public int compare(Integer o1,Integer o2) {
            return o2 - o1;
        }
    });
    // 记录偶数个还是奇数个
    int count = 0;
    // 每次插入小顶堆的是当前大顶堆中最大的数
    // 每次插入大顶堆的是当前小顶堆中最小的数
    // 这样可以保证小顶堆中的数永远大于等于大顶堆中的数
    // 中位数就可以方便地从两者的根结点中获取了
    // 优先队列中的常用方法有：增加元素，删除栈顶，获得栈顶元素，和队列中的几个函数应该是一样的
    // offer peak poll
    public void Insert(Integer num) {
        // 个数为偶数的话，则先插入到大顶堆，然后将大顶堆中最大的数插入到小顶堆
        if(count % 2 == 0) {
            maxHeap.offer(num);
            int max = maxHeap.poll();
            minHeap.offer(max);
        }
        // 个数为奇数的话，则先插入到小顶堆，然后将小顶堆中最小的数插入到大顶堆
        else {
            minHeap.offer(num);
            int min = minHeap.poll();
            maxHeap.offer(min);
        }
        count++;
    }

    public Double GetMedian() {
        // 当前为偶数个，则取小顶堆和大顶堆的堆顶元素求平均
        if(count % 2 == 0) {
            return new Double(minHeap.peek() + maxHeap.peek())/2;
        }
        else {
            return new Double(minHeap.peek());
        }
    }
}