題解 | 【清晰圖解】劍指Offer41.#數(shù)據(jù)流中的中位數(shù)#

默認(rèn)你已經(jīng)理解清楚題意

思路如下

題目的要求是要獲取一個(gè)數(shù)據(jù)流排序后的中位數(shù)，那么我們可以用兩個(gè)優(yōu)先隊(duì)列（堆）來(lái)實(shí)現(xiàn)。

該題用一個(gè)大頂堆，一個(gè)小頂堆來(lái)完成。

大頂堆的每個(gè)節(jié)點(diǎn)的值都大于等于左右孩子節(jié)點(diǎn)的值，也就是說堆頂是最大值。
小頂堆的每個(gè)節(jié)點(diǎn)的值都小于等于左右孩子節(jié)點(diǎn)的值，堆頂也就是最小值。

所以我們用 大頂堆(maxHeap) 來(lái)存數(shù)據(jù)流中比較小一半的值，用 小頂堆(minHeap) 來(lái)存數(shù)據(jù)流中較大一半的值?！按箜敹训亩秧敗迸c“小頂堆的堆頂”也就是排序數(shù)據(jù)流的兩個(gè)中位數(shù)。

估計(jì)你還是理解不了，看下面圖，你看大頂堆(maxHeap)置于下方，小頂堆(minHeap)倒置于上方，兩個(gè)堆組合起來(lái)像一個(gè)沙漏的形狀。

根據(jù)堆的性質(zhì)，我們可以判斷兩個(gè)堆的值從下往上遞增的：

maxHeap堆底 <= maxHeap堆頂 <= minHeap堆頂 <= minHeap堆底。

alt 題目要求獲取數(shù)據(jù)流排序后的中位數(shù)，我們根據(jù)數(shù)據(jù)流的奇偶性以及堆的性質(zhì)，把獲取中位數(shù)的情況分為兩類：

如果數(shù)據(jù)流的個(gè)數(shù)為奇數(shù)時(shí)，保證兩個(gè)堆的高度相差1，那么長(zhǎng)度較大堆的堆頂就是中位數(shù)；
如果數(shù)據(jù)流的個(gè)數(shù)為偶數(shù)時(shí)，保證兩個(gè)堆的高度相等，兩個(gè)堆的堆頂相加除二就是中位數(shù)。

所以我們要保證每次插入元素后，兩堆維持相對(duì)長(zhǎng)度。讓minHeap為長(zhǎng)度較大的堆，每次要插入元素時(shí)進(jìn)行判斷：

當(dāng)兩個(gè)堆總長(zhǎng)度為偶數(shù)的時(shí)候，說明兩堆的高度是相等的，然后把新元素插入到minHeap，插入后minHeap比maxHeap高度大1；
當(dāng)兩堆總長(zhǎng)度為奇數(shù)的時(shí)候，即兩堆高度是不等的，把新元素插入到maxHeap，插入后兩堆高度相等；

我們還要保證插入元素后，兩堆仍然保證是從下往上遞增的順序的。比如上面的偶數(shù)情況，把新元素x直接插入到minHeap，是有可能破壞兩堆的順序性的哦，例如：（minHeap是存儲(chǔ)“較大一半”的值的那個(gè)堆）

假如x的值恰好為“較大一半”，直接插入到“較大一半”的minHeap中，是不會(huì)破壞順序的；
假如x的值為“較小一半”，而此時(shí)你卻插入到“較大一半”的minHeap中，它是會(huì)破壞順序的。

那么，每次新元素插入時(shí)，都需要先插入到另一個(gè)堆，然后進(jìn)行重新排序后，再把最值拿出來(lái)插入正確的堆里面。

最終得出的結(jié)論：

當(dāng)兩堆的總大小是偶數(shù)的時(shí)候，即兩堆大小是相等的，先把新元素插入maxHeap，然后重新排序后把新的最值拿出來(lái)插入到minHeap；
當(dāng)兩堆總大小為奇數(shù)的時(shí)候，則兩堆大小是不等的，先將新元素插入minHeap，然后重新排序后把新的最值拿出并插入到maxHeap；

//Java的代碼
class MedianFinder {
    // 大頂堆存儲(chǔ)較小一半的值
    PriorityQueue<Integer> maxHeap;
    // 小頂堆存儲(chǔ)較大一半的值
    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) {
        // 長(zhǎng)度為奇數(shù)時(shí)先放入小頂堆,重新排序后在插入到大頂堆
        if(maxHeap.si***Heap.si***Heap.add(num);
            maxHeap.add(minHeap.poll());
        } else {
            // 長(zhǎng)度為偶數(shù)時(shí)先放入大頂堆,重新排序后在插入到小頂堆
            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;
        }
    }
}