堆

二叉堆

二叉堆的特性:

• 父节点的键值总是大于或者等于（小于或等于）任何一个子节点的键值
• 每个节点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）

c++实现

struct Heap {
    vector<int> data = {0}; // 下标从1开始，1之后的节点k的父节点为k / 2
    void percolate_up(int k) {
        while(k > 1 && data[k / 2] < data[k]) {
            swap(data[k], data[k / 2]);
            k /= 2;
        }
    }
    void percolate_down(int k) {
        while (2 * k < data.size())
        {
            int j = k * 2;
            if(j + 1 < data.size() && data[j + 1] > data[j]) {
                j = j + 1;
            }
            if(data[k] >= data[j]) {
                break;
            }
            swap(data[j], data[k]);
            k = j;
        }
    }
    void insert(int v) { // 插入一个数
        data.push_back(v);
        percolate_up(data.size() - 1);
    }
    int pop() { // 弹出堆顶元素
        int ret = data[1];
        swap(data[1], data[data.size() - 1]);
        data.pop_back();
        percolate_down(1);
        return ret;
    }
};

对顶堆

对顶堆是由一个大顶堆和一个小顶堆组合而成的数据结构，对顶堆用于动态维护第k大的数。在对顶堆中，小根堆位于大根堆的上方，要保证小根堆的所有数始终比大根堆大。

前i个数的中位数

每次一个数字来了之后，将其与两个队列的队首进行比较，选择该数字加入的队列，然后一直维护着两个队列元素数量的平衡，两个队列元素数量差不超过2即可。每次让求中位数时，中位数就是位于元素数量多1的那个的队列的队首。

int n;
cin >> n;
priority_queue<int> q2;
priority_queue<int, vector<int>, greater<int>> q1;
for(int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if(i == 0) {
        q1.push(x);
    }else {
        int k = q1.top();
        if(x > k) {
            q1.push(x);
        }else {
            q2.push(x);
        }
    }
    if(q1.size() - q2.size() == 2) {
        q2.push(q1.top());
        q1.pop();
    }
    if(q2.size() - q1.size() == 2) {
        q1.push(q2.top());
        q2.pop();
    }
    if(q1.size() > q2.size()) {
        cout << q1.top() << endl;
    }else {
        cout << q2.top() << endl;
    }
}

第k小的数

例题: 输入长度为 的序列 ，长度为 的序列 , 依次插入 中的元素。对于每一个 ，查询插入 中第 个元素后第 小的数。

int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for(int i = 0; i < n; i++) {
    cin >> a[i];
}
for(int i = 0; i < n; i++) {
    cin >> b[i];
}
int k = 1;
priority_queue<int, vector<int>, greater<int>> q1;
priority_queue<int> q2;
for(int i = 0; i < n; i++) {
    q2.push(a[i]);
    if(q2.size() > k) {
        q1.push(q2.top());
        q2.pop();
    }
    while(k <= m && i + 1 == b[k-1]) {
        cout << q2.top() << endl;
        k++;
        if(q1.size()) {
            q2.push(q1.top());
            q1.pop();
        }
    }
}