$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

笔记：
在上一次的题解中我们已经把这几种操作给列了出来。
这次只需要再额外存储两个变量：

//ph[k]表示第k个插入的点，在堆里的下标是？
//hp[k]表示下标为k的点，是第几个插入的点？

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int h[N], hp[N], ph[N], hsize, m;
//ph[k]表示第k个插入的点，在堆里的下标是？
//hp[k]表示下标为k的点，是第几个插入的点？
void heap(int a, int b) {  //交换
    swap(h[a], h[b]);
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
}
void down(int u) {
    int t = u;
    if (u * 2 <= hsize && h[t] > h[2 * u]) t = 2 * u;
    if (u * 2 + 1 <= hsize & h[t] > h[2 * u + 1]) t = 2 * u + 1;
    if (t != u) {
        heap(t, u);
        down(t);
    }
}
void up(int u) {
    while (u / 2 && h[u / 2] > h[u]) {
        heap(u, u / 2);
        u /= 2;
    }
}
int main() {
    int n; cin>>n;
    while (n--) {
        string s; cin>>s;
        if (s[0] == 'I') {
            int x; cin>>x;
            h[++hsize] = x;
            hp[hsize] = ++m;
            ph[m] = hsize;
            up(hsize);
        }
        else if (s[0] == 'P') cout<<h[1] << endl;
        else if (s == "DM") {
            heap(1, hsize);
            hsize--;
            down(1);
        }
        else if (s == "D") {
            int k; cin>>k;
            k = ph[k];
            heap(k, hsize); hsize --;
            up(k); down(k);
        }else {
            int k, x; cin>>k>>x;
            h[ph[k]] = x;
            up(ph[k]); down(ph[k]);
        }
    }
}