题解 | 【清晰图解】剑指Offer41.#数据流中的中位数#

默认你已经理解清楚题意

思路如下

题目的要求是要获取一个数据流排序后的中位数，那么我们可以用两个优先队列（堆）来实现。

该题用一个大顶堆，一个小顶堆来完成。

大顶堆的每个节点的值都大于等于左右孩子节点的值，也就是说堆顶是最大值。
小顶堆的每个节点的值都小于等于左右孩子节点的值，堆顶也就是最小值。

所以我们用 大顶堆(maxHeap) 来存数据流中比较小一半的值，用 小顶堆(minHeap) 来存数据流中较大一半的值。“大顶堆的堆顶”与“小顶堆的堆顶”也就是排序数据流的两个中位数。

估计你还是理解不了，看下面图，你看大顶堆(maxHeap)置于下方，小顶堆(minHeap)倒置于上方，两个堆组合起来像一个沙漏的形状。

根据堆的性质，我们可以判断两个堆的值从下往上递增的：

maxHeap堆底 <= maxHeap堆顶 <= minHeap堆顶 <= minHeap堆底。

alt 题目要求获取数据流排序后的中位数，我们根据数据流的奇偶性以及堆的性质，把获取中位数的情况分为两类：

如果数据流的个数为奇数时，保证两个堆的高度相差1，那么长度较大堆的堆顶就是中位数；
如果数据流的个数为偶数时，保证两个堆的高度相等，两个堆的堆顶相加除二就是中位数。

所以我们要保证每次插入元素后，两堆维持相对长度。让minHeap为长度较大的堆，每次要插入元素时进行判断：

当两个堆总长度为偶数的时候，说明两堆的高度是相等的，然后把新元素插入到minHeap，插入后minHeap比maxHeap高度大1；
当两堆总长度为奇数的时候，即两堆高度是不等的，把新元素插入到maxHeap，插入后两堆高度相等；

我们还要保证插入元素后，两堆仍然保证是从下往上递增的顺序的。比如上面的偶数情况，把新元素x直接插入到minHeap，是有可能破坏两堆的顺序性的哦，例如：（minHeap是存储“较大一半”的值的那个堆）

假如x的值恰好为“较大一半”，直接插入到“较大一半”的minHeap中，是不会破坏顺序的；
假如x的值为“较小一半”，而此时你却插入到“较大一半”的minHeap中，它是会破坏顺序的。

那么，每次新元素插入时，都需要先插入到另一个堆，然后进行重新排序后，再把最值拿出来插入正确的堆里面。

最终得出的结论：

当两堆的总大小是偶数的时候，即两堆大小是相等的，先把新元素插入maxHeap，然后重新排序后把新的最值拿出来插入到minHeap；
当两堆总大小为奇数的时候，则两堆大小是不等的，先将新元素插入minHeap，然后重新排序后把新的最值拿出并插入到maxHeap；

//Java的代码
class MedianFinder {
    // 大顶堆存储较小一半的值
    PriorityQueue<Integer> maxHeap;
    // 小顶堆存储较大一半的值
    PriorityQueue<Integer> minHeap;
  
    /** initialize your data structure here. */
    public MedianFinder() {
        maxHeap = new PriorityQueue<Integer>((x, y) -> (y - x));
        minHeap = new PriorityQueue<Integer>();
    }
    
    public void addNum(int num) {
        // 长度为奇数时先放入小顶堆,重新排序后在插入到大顶堆
        if(maxHeap.si***Heap.si***Heap.add(num);
            maxHeap.add(minHeap.poll());
        } else {
            // 长度为偶数时先放入大顶堆,重新排序后在插入到小顶堆
            maxHeap.add(num);
            minHeap.add(maxHeap.poll());
        }
    }
    
    public double findMedian() {
        if(maxHeap.si***Heap.size()) {
            return minHeap.peek();
        } else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
}