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

大家好，欢迎来到IT知识分享网。

假如有5亿个int，寻找它们的中位数。

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*\sum_{i=1}^{n/2} \log_2 i$。

c++代码：

int median_heap(const vector<int>& arr) { if(arr.empty()) return -1; if(arr.size() == 1) return arr[0]; else if(arr.size() == 2) return (arr[0]+arr[1])/2; priority_queue<int> maxheap; priority_queue<int, vector<int>, greater<int>> minheap; maxheap.push(min(arr[0],arr[1])); minheap.push(max(arr[0],arr[1])); auto i=arr.begin()+2; 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())/2; }

参考
十道海量数据处理面试题与十个方法大总结
利用最大堆和最小堆在线寻找中位数