poj 3784 用堆动态求解中位数

堆真是一种简单而又神奇的数据结构，以前用它求过前kth的数，现在又可以用两个堆来动态求解中位数。

算法：

　　构建一个大顶堆和一个小顶堆，分别记为g和l。

　　假设当前中位数为mid，新读入一个数为tmp，则：

　　1.如果tmp < mid，则将tmp插入大顶堆，跳到步骤3。

　　2.如果tmp >= mid，则将tmp插入小顶堆，跳到步骤4。

　　3.如果大顶堆的元素个数比小顶堆多2（两个堆个数不平衡），则将mid插入小顶堆，弹出大顶堆堆顶元素为新的mid。

　　4.与步骤3相反，如果小顶堆的元素个数比大顶堆多2，则将mid插入大顶堆，弹出小顶堆堆顶元素为新的mid。

　　5.如果两个堆元素个数相同，则mid即为当前序列的中位数；否则，中位数为mid和元素个数较多的堆的堆顶元素的平均值，至此算法描述结束。

也有人把这个叫做最大最小堆或者是对顶堆的。

示例代码poj3784：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;

priority_queue<int, vector<int>, less<int> > g;
priority_queue<int, vector<int>, greater<int> > l;
const int N = 10000;
int ans[N];
int p;

int main ()
{
    int t;
    scanf("%d", &t);
    while ( t-- )
    {
        int _case, n, mid;
        scanf("%d%d%d", &_case, &n, &mid);
        printf("%d %d
", _case, ( n + 1 ) / 2);
        p = 0;
        ans[p++] = mid;
        while ( !l.empty() ) l.pop();
        while ( !g.empty() ) g.pop();
        for ( int i = 2; i <= n; i++ )
        {
            int tmp;
            scanf("%d", &tmp);
            if ( tmp < mid )
            {
                g.push(tmp);
                if ( g.size() - l.size() == 2 )
                {
                    l.push(mid);
                    mid = g.top();
                    g.pop();
                }
            }
            else
            {
                l.push(tmp);
                if ( l.size() - g.size() == 2 )
                {
                    g.push(mid);
                    mid = l.top();
                    l.pop();
                }
            }
            if ( i & 1 )
            {
                ans[p++] = mid;
            }
        }
        for ( int i = 0; i < p; i++ )
        {
            printf("%d", ans[i]);
            if ( i % 10 == 9 || i == p - 1 )
            {
                putchar('
');
            }
            else
            {
                putchar(' ');
            }
        }
    }
    return 0;
}