以小根堆为例
down和up为核心操作
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
#define nn 111111
void down(int);
void up(int);
void dt(int t);
void _swap(int ,int);
int h[nn], hp[nn], ph[nn],idx=0;
string s;
int k, x;
int m = 0;
void down(int u)
{
int t = u;
if (2 * u <= idx && h[t] > h[2 * u])t = 2 * u;
if (2 * u + 1 <= idx && h[t] > h[2 * u + 1])t = 2 * u + 1;
if (t != u)
{
_swap(u, t);
down(t);
}
}
void _swap(int a, int b)
{
swap(h[a], h[b]);
swap(ph[hp[a]], ph[hp[b]]);
swap(hp[a], hp[b]);
}
void dt(int k)
{
_swap(k, idx);
idx--;
up(k); down(k);
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
_swap(u , u / 2);
u /= 2;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
int k, x;
while (n--)
{
cin >> s;
if (s == "I")
{
cin >> x;
h[++idx] = x;
ph[++m] = idx;
hp[idx] = m;
up(idx);
}
if (s == "PM")
{
cout << h[1] << '\n';
}
if (s == "DM")
{
_swap(1, idx);
idx--;
down(1);
}
if (s == "D")
{
cin >> k;
dt(ph[k]);
}
if (s == "C")
{
cin >> k >> x;
h[ph[k]] = x;
down(ph[k]);up(ph[k]);
}
}
}