数据流的中位数

题目：

对于数据流问题，需要设计一个在线系统，这个系统不断的接受一些数据，并维护这些数据的一些信息。中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

请设计一个支持以下两种操作的系统：
+num——从数据流中添加一个整数 \(k\) 到系统中\((0 \leq k \leq 2^{32})\)。
? ——返回目前所有元素的中位数。

格式：

输入格式：

第一行输入一个整型 \(n(n\leq100000)\)

第二行输入 \(n\) 个操作

输出格式：

? 询问时输出中位数，每个操作一行，保证每次查询都合法

样例：

输出：

5
+ 1
+ 2
?
+ 3
?

输出：

1.5
2

思路：

维护两个堆，小顶堆堆头为最大数，大顶堆堆头为最小数。

代码:

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

const int N = 100000;
priority_queue<int, vector<int>, less<int>> q1; // 大顶堆，存小一半的数
priority_queue<int, vector<int>, greater<int>> q2; // 小顶堆，存大一半的数

void insert (int num) {
    if (q1.size() > q2.size()) {
        q1.push(num);
        q2.push(q1.top());
        q1.pop();
    } else {
        q1.push(num);
        if (q2.size() != 0 && q1.top() > q2.top()) {
            q2.push(q1.top());
            q1.pop();
            q1.push(q2.top());
            q2.pop();
        }
    }
}

int main() {
    int n, num;
    cin >> n;
    while (n--) {
        char ch;
        cin >> ch;
        if (ch == '+') {
            cin >> num;
            insert(num);
        } else {
            if (q1.size() > q2.size()) {
                cout << q1.top() << endl;
            } else {
                cout << (float)(q1.top() + q2.top()) / 2 << endl;
            }
        }
    }
    return 0;
}