算法竞赛进阶指南：动态中位数

依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。

使用对顶堆算法：建立两个二叉堆（一个大根堆一个小根堆）

    int m, n;
    cin >> m >> n;
    priority_queue<int> max_heap; // 大根堆，存储1~M/2的整数
    priority_queue<int, vector<int>, greater<int>> min_heap; // 小根堆，存储M/2 ~ M的整数
    // 小根堆的堆顶即为序列的中位数
    // 读入一个数后，比中位数小则插入大根堆，否则插入小根堆

    printf("%d %d\n", m, (n + 1 ) / 2);
    int cnt = 0;
    for( int i =1; i <= n; i++ )
    {
        int t;
        scanf("%d", &t);
        max_heap.push(t);
        if ( min_heap.size() && min_heap.top() < max_heap.top())
        {
            auto a = min_heap.top(), b = max_heap.top();
            min_heap.pop(), max_heap.pop();
            min_heap.push(b), max_heap.push(a);
        }
         // 一个堆中元素过多，就要取出该堆的堆顶放入另一个堆
        if( max_heap.size() > min_heap.size() + 1 )
        {
            min_heap.push( max_heap.top() );
            max_heap.pop();
        }

        if( i  % 2 )
        {
            printf("%d ", max_heap.top());
            if( ++ cnt % 10 == 0 ) printf("\n");
        }

    }