每日算法：數據流的中位數

作者： sisterAn 2021-10-27 10:43:36

開發前端算法

如果插入元素比大頂堆的堆頂要大，則將該元素插入到小頂堆中；如果要小，則插入到大頂堆中。

[[431427]]

本文轉載自微信公眾號「三分鐘學前端」，作者sisterAn 。轉載本文請聯系三分鐘學前端公眾號。

中位數是有序列表中間的數。如果列表長度是偶數，中位數則是中間兩個數的平均值。

例如，

[2,3,4] 的中位數是 3

[2,3] 的中位數是 (2 + 3) / 2 = 2.5

設計一個支持以下兩種操作的數據結構：

void addNum(int num)- 從數據流中添加一個整數到數據結構中。
double findMedian() - 返回目前所有元素的中位數。

示例：

addNum(1) 
addNum(2) 
findMedian() -> 1.5 
addNum(3)  
findMedian() -> 2

進階:

如果數據流中所有整數都在 0 到 100 范圍內，你將如何優化你的算法?
如果數據流中 99% 的整數都在 0 到 100 范圍內，你將如何優化你的算法?

看到這個動態數組獲取中位數問題，不要太激動，這太適合使用堆了，考察的就是堆的經典應用：中位數問題，詳情可查看前端進階算法9：看完這篇，再也不怕堆排序、Top K、中位數問題面試了

解法：利用堆

解題思路：

這里需要維護兩個堆：

大頂堆：用來存取前 n/2 個小元素，如果 n 為奇數，則用來存取前 Math.floor(n/2) + 1 個元素
小頂堆：用來存取后 n/2 個小元素

那么，根據題目要求，中位數就為：

n 為奇數：中位數是大頂堆的堆頂元素
n 為偶數：中位數是大頂堆的堆頂元素與小頂堆的堆頂元素的平均值

當數組為動態數組時，每當數組中插入一個元素時，都需要如何調整堆喃?

如果插入元素比大頂堆的堆頂要大，則將該元素插入到小頂堆中;如果要小，則插入到大頂堆中。

當插入完成后，如果大頂堆、小頂堆中元素的個數不滿足我們已上的要求，我們就需要不斷的將大頂堆的堆頂元素或小頂堆的堆頂元素移動到另一個堆中，直到滿足要求

代碼實現：

let MedianFinder = function() { 
    // 大頂堆，用來保存前 n/2 小的元素 
    this.lowHeap = new MaxHeap() 
    // 小頂堆，用來保存后 n/2 小的元素 
    this.hightHeap = new MinHeap() 
}; 
// 插入元素 
MedianFinder.prototype.addNum = function(num) { 
    // 如果大頂堆為空或大頂堆堆頂元素小于num，則插入大頂堆 
    // 否則插入到小頂堆中 
    if(!this.lowHeap.getSize() || num < this.lowHeap.getHead()) { 
        // 比大頂堆的堆頂小，插入到大頂堆中 
        this.lowHeap.insert(num) 
    } else { 
        // 比小頂堆的堆頂大，插入到小頂堆中 
        this.hightHeap.insert(num) 
    } 
 
    // 比較大小頂堆的是否依然保持平衡 
    if(this.lowHeap.getSize() - this.hightHeap.getSize() > 1) { 
        // 大頂堆往小頂堆遷移 
        this.hightHeap.insert(this.lowHeap.removeHead()) 
    } 
    if(this.hightHeap.getSize() > this.lowHeap.getSize()) { 
        // 小頂堆向大頂堆遷移 
        this.lowHeap.insert(this.hightHeap.removeHead()) 
    } 
}; 
// 獲取中位數 
MedianFinder.prototype.findMedian = function() { 
    if(this.lowHeap.getSize() && this.lowHeap.getSize() === this.hightHeap.getSize()) { 
        return (this.lowHeap.getHead() + this.hightHeap.getHead())/2 
    } 
    return this.lowHeap.getHead() 
};

其中小頂堆定義：

// 小頂堆 
let MinHeap = function() { 
    let heap = [,] 
    // 堆中元素數量 
    this.getSize = ()=> heap.length - 1 
    // 插入 
    this.insert = (key) => { 
        heap.push(key) 
        // 獲取存儲位置 
        let i = heap.length-1 
        while (Math.floor(i/2) > 0 && heap[i] < heap[Math.floor(i/2)]) {   
            swap(heap, i, Math.floor(i/2)); // 交換  
            i = Math.floor(i/2);  
        } 
    } 
    // 刪除堆頭并返回 
    this.removeHead = () => { 
        if(heap.length > 1) { 
            if(heap.length === 2) return heap.pop() 
            let num = heap[1] 
            heap[1] = heap.pop() 
            heapify(1) 
            return num 
        } 
        return null 
    } 
    // 獲取堆頭 
    this.getHead = () => { 
        return heap.length > 1 ? heap[1]:null 
    } 
    // 堆化 
    let heapify = (i) => { 
        let k = heap.length-1 
        // 自上而下式堆化 
        while(true) { 
            let minIndex = i 
            if(2*i <= k && heap[2*i] < heap[i]) { 
                minIndex = 2*i 
            } 
            if(2*i+1 <= k && heap[2*i+1] < heap[minIndex]) { 
                minIndex = 2*i+1 
            } 
            if(minIndex !== i) { 
                swap(heap, i, minIndex) 
                i = minIndex 
            } else { 
                break 
            } 
        } 
    }  
    let swap = (arr, i, j) => { 
        let temp = arr[i] 
        arr[i] = arr[j] 
        arr[j] = temp 
    } 
}

大頂堆定義：

// 大頂堆 
let MaxHeap = function() { 
    let heap = [,] 
    // 堆中元素數量 
    this.getSize = ()=>heap.length - 1 
    // 插入大頂堆 
    this.insert = (key) => { 
        heap.push(key) 
        // 獲取存儲位置 
        let i = heap.length-1 
        while (Math.floor(i/2) > 0 && heap[i] > heap[Math.floor(i/2)]) {   
            swap(heap, i, Math.floor(i/2)); // 交換  
            i = Math.floor(i/2);  
        } 
    } 
    // 獲取堆頭 
    this.getHead = () => { 
        return heap.length > 1 ? heap[1]:null 
    } 
    // 刪除堆頭并返回 
    this.removeHead = () => { 
        if(heap.length > 1) { 
            if(heap.length === 2) return heap.pop() 
            let num = heap[1] 
            heap[1] = heap.pop() 
            heapify(1) 
            return num 
        } 
        return null 
    } 
    // 堆化 
    let heapify = (i) => { 
        let k = heap.length-1 
        // 自上而下式堆化 
        while(true) { 
            let maxIndex = i 
            if(2*i <= k && heap[2*i] > heap[i]) { 
                maxIndex = 2*i 
            } 
            if(2*i+1 <= k && heap[2*i+1] > heap[maxIndex]) { 
                maxIndex = 2*i+1 
            } 
            if(maxIndex !== i) { 
                swap(heap, i, maxIndex) 
                i = maxIndex 
            } else { 
                break 
            } 
        } 
    }  
    let swap = (arr, i, j) => { 
        let temp = arr[i] 
        arr[i] = arr[j] 
        arr[j] = temp 
    } 
}