寻找中位数（分治+双堆）

假如有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())/;
}
           

参考

十道海量数据处理面试题与十个方法大总结

利用最大堆和最小堆在线寻找中位数