尋找中位數（分治+雙堆）

假如有5億個int，尋找它們的中位數。

思路是先分治，再用雙堆法：

首先将int劃分為2^16個區域，然後讀取資料統計落到各個區域裡的數的個數，之後我們根據統計結果就可以判斷中位數落到那個區域。然後第二次掃描我們隻統計落在這個區域中的那些數就可以了。

雙堆法的思路：

序列中的元素，前一半存儲在一個最大堆中，後一半存儲在一個最小堆中。控制MaxHeap與MinHeap的大小差不能超過1。具體操作如下：

1.如果 num < MaxHeapTop，則
    1.1 如果 MaxHeapSize <= MinHeapSize，将num插入最大堆；
    1.2 如果 MaxHeapSize >  MinHeapSize，将MaxHeapTop從最大堆中移到最小堆，然後将num插入最大堆。
2.如果 MaxHeapTop <= num <= MinHeapTop，則
    2.1 如果 MaxHeapSize <  MinHeapSize，将num插入最大堆；
    2.2 如果 MaxHeapSize >  MinHeapSize，将num插入最小堆；
    2.3 如果 MaxHeapSize == MinHeapSize，随意插，看心情。
3.如果 num > MinHeapTop，則
    3.1 如果 MaxHeapSize >= MinHeapSize，将num插入最小堆；
    3.2 如果 MaxHeapSize <  MinHeapSize，将MinHeapTop從最小堆中移到最大堆，然後将num插入最小堆。
           

上面的插入情況會保證最大堆和最小堆的元素個數差小于1，中位數就隻在最大堆和最小堆的頂部元素中産生：如果最大堆和最小堆的元素個數相等，則中位數為最大堆和最小堆的頂部元素的平均值；否則，中位數為元素個數多的那個堆的堆頂元素。

複雜度分析：

最差情況每次都要對堆做3次調整，複雜度為 3∗2∗∑n/2i=1log2i 。

c++代碼：

int median_heap(const vector<int>& arr)
{
    if(arr.empty()) return -;
    if(arr.size() == ) return arr[];
    else if(arr.size() == ) return (arr[]+arr[])/;

    priority_queue<int> maxheap;
    priority_queue<int, vector<int>, greater<int>> minheap;
    maxheap.push(min(arr[],arr[]));
    minheap.push(max(arr[],arr[]));

    auto i=arr.begin()+;
    for(;i!=arr.end();++i)
    {
        // 應放入maxheap
        if(*i < maxheap.top())
        {
            if(maxheap.size() > minheap.size())
            {
                minheap.push(maxheap.top());
                maxheap.pop();
            }
            maxheap.push(*i);
        }
        // 應放入minheap
        else if(*i > minheap.top())
        {
            if(maxheap.size() < minheap.size())
            {
                maxheap.push(minheap.top());
                minheap.pop();
            }
            minheap.push(*i);
        }
        else
        {
            if(maxheap.size() < minheap.size())
                maxheap.push(*i);
            else
                minheap.push(*i);
        }
    }

    if(maxheap.size() > minheap.size())
        return maxheap.top();
    else if(maxheap.size() < minheap.size())
        return minheap.top();
    return (maxheap.top()+minheap.top())/;
}
           

參考

十道海量資料處理面試題與十個方法大總結

利用最大堆和最小堆線上尋找中位數