剑指offer07

题目描述

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

解题思路分析

这个题目一看就知道其实需要使用两个堆来实现，或者也可以使用平衡二叉树来实现，但是相对于面试的题目来说，使用平衡二叉树来实现的话代码量太大了，而且一般人都不可能写的出来，所以这里我就使用了Java的PriorityQueue来构建堆来解决这个问题，如果自己去维护两个堆的话，也不是不可以，但是这很考验代码能力。
再来说下本题的思路，利用一个大顶堆（即堆顶为最大的元素）和一个小顶堆（即堆顶为小的元素），然后需要注意的是在插入的时候需要判断元素是插入大顶堆还是插入小顶堆，这里我们采用以下的约定来插入：
1.当是第奇数个元素插入进来时，放到大顶堆，同时需要注意的是插入时候需要保证插入完成之后所有小顶堆的元素都比大顶堆大
2.当是第偶数个元素插入进来时，放到小顶堆，同时需要注意的是插入时候需要保证插入完成之后所有大顶堆的元素都比小顶堆小

代码实现

    private static int count = 0;
    // 建立小顶堆，PriorityQueue默认维护一个小顶堆
    private static PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    // 建立大顶堆，只要改变以下元素入队列时的比较方法就可以改变为大顶堆
    private static PriorityQueue<Integer> maxHeap = new PriorityQueue<>(15, ((o1, o2) -> o2 - o1));

    public void Insert(Integer num) {
        count++;
        // 第偶数个元素入堆，放到小顶堆
        if ((count & 1) == 0) {
            //保证入到小顶堆的元素都比大顶堆大
            if (maxHeap.size() != 0 && num < maxHeap.peek()) {
                maxHeap.offer(num);
                num = maxHeap.poll();
            }
            // 入堆
            minHeap.offer(num);
        // 第奇数个元素入堆，放到大顶堆
        } else {
            // 保证入到大顶堆的元素都比小顶堆小
            if (minHeap.size() != 0 && num > minHeap.peek()) {
                minHeap.offer(num);
                num = minHeap.poll();
            }
            // 入堆
            maxHeap.offer(num);
        }
    }

    public Double GetMedian() {
        // 如果元素为奇数个时，那中位就位大顶堆的堆顶元素
        if ((count & 1) == 1) {
            return (double)maxHeap.peek();
        // 如果元素为偶数个时，那中位数为两个堆顶元素的平均值
        } else {
            return (double)(minHeap.peek() + maxHeap.peek()) / 2;
        }
    }