堆排序:数据流中的中位数

编辑于 2017-02-03

* 移动设备下, 可左滑手指以查看较宽代码

动态的插入数据,取中位数,直接使用 C++ 中的堆。使用两个堆,一个堆的数均小于另一个,最终中位数就在两个堆的堆顶之中。

int count=0;
// 左边一个大顶堆
priority_queue<int, vector<int>, less<int> > big_heap; 
// 右边一个小顶堆
priority_queue<int, vector<int>, greater<int> > small_heap;   
// 大顶堆所有元素均小于等于小顶堆的所有元素
void Insert(int num)
{
    count+=1;
    // 元素个数是偶数时,将小顶堆堆顶放入大顶堆
    if(count%2==0){
        big_heap.push(num);
        small_heap.push(big_heap.top());
        big_heap.pop();
    } else {
        small_heap.push(num);
        big_heap.push(small_heap.top());
        small_heap.pop();
    }
}

double GetMedian()
{
    if(count%2==1)
        return big_heap.top();
    else
        return double((small_heap.top()+big_heap.top())/2.0);
}