https://www.luogu.com.cn/training/661703#problems

#include<bits/stdc++.h>
using namespace std;

int n;
int idx;  //堆里面有idx个
int h[100005];  //堆
int ph[100005];  //ph[k]=u表示第k个进入的数字在h中的u个位置
int hp[100005];  //hp[u]=k表示结点u是第k个进入的数字 	
int m;  //表示第m个插入的数字


void h_swap(int x, int y){
	int k1 = hp[x], k2 = hp[y];
	swap(ph[k1], ph[k2]);	
	swap(hp[x], hp[y]);
	swap(h[x], h[y]);
}

void up(int u){
	if(u / 2 && h[u / 2] > h[u]){
		h_swap(u / 2, u);
		up(u / 2);
	}
}
int main(){
	cin >> n;
	while(n--){
		string op;
		cin >> op;
		if(op == "I"){
			int x;
			cin >> x;
			m++;
			idx++;
			h[idx] = x;
			ph[m] = idx;  //第m个插入的数字在结点idx
			hp[idx] = m;  //结点idx是第m个插入的数字
			up(idx);
		}
		else if(op == "PM") cout << h[1] << endl;
		else if(op == "DM"){
			del(1);
		}
		else if(op == "D"){
			int k;
			cin >> k;
			int u = ph[k];  //要删除结点u
			del(u);
		}
		else if(op == "C"){
			int k, x;
			cin >> k >> x;
			int u = ph[k];
			h[u] = x;
			up(u);
			down(u);
		}
		
	}
	return 0;
}

堆：
	小根堆：根结点一定最小
	大根堆：根结点一定最大
	操作：
		插入：up操作O(log(n)),
		删除最小值:down操作O(log(n))
		删除第k个插入的数字:down操作一遍，up操作一遍，O(log(n))
		输出最小值:O(1)
	堆排序整体时间复杂度：O(n * log(n));

	h数组：堆数组
	kh:本来输入的第k个数字，存到了h数组中的kh[k]