题目链接

算法竞赛进阶指南-20.动态中位数

Method : 对顶堆

具体思路大致是，维护两个堆：一个大根堆，一个小根堆。然后小于中位数的都放在大根堆，大于中位数的都放在小根堆，这样的两个堆就构成了一个对顶堆。

当序列的个数为奇数时，中位数恰好为主导堆的堆顶；当序列的个数为偶数时，中位数为两个堆顶的平均数。

如何维护这个对顶堆？

1. 当小根堆的最小值<大根堆的最大值时，交换堆顶。

min_heap.top() < max_heap.top()

2. 如果某个堆的个数大于了当前序列的${\frac{1}{2}}$，那么就将多余的堆顶移到另一个堆，直到两个堆数量相等或只相差1。

abs(max_heap.size() - min_heap.size()) > 1

[代码1]: 以大根堆为主导

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

const int M = 1e6 + 7;

int p;

int main() {
    cin >> p;
    
    while (p --) {
        int id, m;
        scanf("%d %d", &id, &m);
        printf("%d %d\n", id, (m + 1) / 2);
        
        priority_queue<int> max_heap;
        priority_queue<int, vector<int>, greater<int>> min_heap; 
        int cnt = 0;
        for (int i = 1; i <= m; 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(); auto 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 & 1) {
                cnt ++;
                printf("%d ", max_heap.top());
                if (cnt % 10 == 0) puts("");
            }
        }
        if (cnt % 10) puts(""); // 最后一行不满足10个也要换行
    }
    
    return 0;
}

[代码2]: 以小根堆为主导

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>

using namespace std;

const int M = 1e6 + 7;

int p;

int main() {
    cin >> p;
    
    while (p --) {
        int id, m;
        scanf("%d %d", &id, &m);
        printf("%d %d\n", id, (m + 1) / 2);
        
        priority_queue<int> max_heap;
        priority_queue<int, vector<int>, greater<int>> min_heap; 
        int cnt = 0;
        for (int i = 1; i <= m; i ++) {
            int t;
            scanf("%d", &t);
            min_heap.push(t);
            // 维护对顶堆
            if (max_heap.size() && min_heap.top() < max_heap.top()) {
                auto a = min_heap.top(); auto b = max_heap.top();
                min_heap.pop(); max_heap.pop();
                min_heap.push(b); max_heap.push(a);
            }
            
            if (min_heap.size() - max_heap.size() > 1) {
                max_heap.push(min_heap.top());
                min_heap.pop();
            }
            
            // 奇数输出
            if (i & 1) {
                cnt ++;
                printf("%d ", min_heap.top());
                if (cnt % 10 == 0) puts("");
            }
        }
        if (cnt % 10) puts(""); // 最后一行不满足10个也要换行
    }
    
    return 0;
}

复杂度分析

• 时间复杂度${O(nlog_2n)}$， 其中$nlog_2n$是调整堆的时间复杂度。

• 空间复杂度${O(n)}$， 其中n是建堆所需要的空间。