模拟堆

我们来看这个题，首先，他要我们实现一个堆的操作对吧。那实现堆，我们就要谈到两个函数 $ down $ 和 $ up $。

void down(int u) { //当前堆的元素下沉
    int t = u; //让t代指u以及其两个儿子（三个点）中的最大值
    if (u * 2 <= cnt && h[u * 2] < h[t])t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t])t = u * 2 + 1; //注意此处为d[t]
    if (u != t) { //最小值不是t，那么下沉，并且继续down操作
        heap_swap(u, t);
        down(t);
    }
}
void up(int u) {
    while (u / 2 && h[u / 2] > h[u]) { //第一个u/2是防止当u冲到顶然后陷入死循环
        heap_swap(u / 2, u);
        u /= 2;
    }
}

知道这两个函数之后，我们就可以进行写题了。当然，我们还要知道一些插入与删除操作，我们只需要把这个堆当作链表来看就行了。

代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m = 0; 
int h[N], ph[N], hp[N], cnt;
void heap_swap(int a, int b) { 
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]); 
    swap(h[a], h[b]); 
}
void down(int u) { 
    int t = u; 
    if (u * 2 <= cnt && h[u * 2] < h[t])t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t])t = u * 2 + 1;
    if (u != t) { 
        heap_swap(u, t);
        down(t);
    }
}
void up(int u) {
    while (u / 2 && h[u / 2] > h[u]) { 
        heap_swap(u / 2, u);
        u /= 2;
    }
}
int main() {
    cin >> n;
    while (n--) {
        string op;
        int k, x;
        cin >> op;
        if (op == "I") {
            cin >> x;
            cnt++, m++; 
            ph[m] = cnt; 
            hp[cnt] = m; 
            h[cnt] = x;
            up(cnt);
        } else if (op == "PM") {
            cout << h[1] << endl;
        } else if (op == "DM") {
            heap_swap(1, cnt);
            cnt--;
            down(1);
        } else if (op == "D") {
            cin >> k; 
            k = ph[k]; 
            heap_swap(k, cnt); 
            cnt--;
            down(k);
            up(k);
        } else { 
            cin >> k >> x;
            k = ph[k]; 
            h[k] = x;
            down(k);
            up(k);
        }
    }
    return 0;
}