模拟堆

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int h[N];
int s;
int ph[N], hp[N];//ph[i]存的是第i插入数的下标， hp[i]存的是第i个点在hp数组里的下标 ph[j] = k, hp[k] = j;
int cnt;
void head_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(h[a], h[b]);
    swap(hp[a], hp[b]);
}
void down(int u)
{
    int t = u;
    if(u * 2 <= s && h[u * 2 ] < h[t])t = u * 2;
    if(u * 2 + 1 <= s && h[u * 2 + 1] < h[t])t = u * 2 + 1;
    if(u != t)
    {
        head_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    if(h[u / 2] > h[u] && u / 2)
    {
        head_swap(u, u / 2);
        up(u / 2);
    }
}

int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        string ss;
        int  k, c;
        cin >> ss;
        if(ss == "PM")
        {
            cout << h[1]<<endl;
        }
        if(ss == "I")
        {
            cin >> c;
            cnt ++, s ++;
            h[s] = c;
            ph[cnt] = s, hp[s] = cnt;
            up(s);
        }
        if(ss == "DM")
        {
            head_swap(1, s);
            s --;
            down(1);
        }
        if( ss == "D")
        {
            cin >> k;
            k = ph[k];
            head_swap(k, s);
            s --;
            down(k), up(k);
        }
        if( ss == "C")
        {
            cin >> k >> c;
            k = ph[k];
            h[k] = c;
            down(k), up(k);
        }
    }
    return 0;
}

链接