题目传送门
一、手写堆的实现
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int h[N]; //堆数组
int ph[N], hp[N];
//ph[i] i:插入点的序号，值:堆里的位置
//hp[j] j:堆里的位置， 值：插入点的序号
int cnt;
/**
功能：交换堆中两个结点（按堆中坐标位置调整，不是输入序号）
因为每个结点，其实是三个属性:值、输入序号、堆中位置，调整两个结点，
需要同时修改三个属性. 我们现在知道的是堆中位置,
(1)按堆中位置，可以直接修改值：swap(h[a],h[b]);
(2)预交换两个结点的原始输入序号，就是swap(hp[a],hp[b]);
(3)预交换两个结点的堆中位置记录，就是ph[hp[a]],ph[hp[b]];
* @param a 堆中位置a
* @param b 堆中位置b
*/
void heap_swap(int a, int b) {
swap(h[a], h[b]);
swap(hp[a], hp[b]);
swap(ph[hp[a]], ph[hp[b]]);
}
/**
* 功能：在堆中向下调整
* @param u
*/
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);
}
}
/**
* 功能:在堆中向上调整
* @param u
*/
void up(int u) {
while (u / 2 && h[u] < h[u / 2]) {
heap_swap(u, u / 2);
u >>= 1;
}
}
int n, m;
int main() {
//输入优化
ios::sync_with_stdio(false);
cin >> n;
while (n--) {
string op;
int k, x;
cin >> op;
//向堆中插入一个元素
if (op == "I") {
cin >> x;
/**
1、尾部插入元素
每插入一个数字，cnt++，cnt为堆里元素的个数，
因为堆里的元素可以增加和减少，所以堆里的数据和向堆里插入的数据
大概率是不一样的，m>=cnt。
2、维护三个信息
（1）新元素放入堆中
（2）记录输入序号与堆中索引的关系（正向）
（3）记录堆中索引与输入序号的关系（反向）
*/
m++;//输入总数+1
cnt++;//开辟一个新的数组空间，用来装第m个元素
//记录映射关系
//(1)第m个插入的元素，在堆中的下标为cnt
ph[m] = cnt;
//(2)在堆中以cnt为下标的节点，是第m个插入的
hp[cnt] = m;
//(3)在最后一个数组位置上记录数值x
h[cnt] = x;
//找到此元素的合适位置，保持堆的特性
up(cnt);
}
//输出最小值
if (op == "PM")printf("%d
", h[1]);
//删除最小值
if (op == "DM") {
//尾删法
heap_swap(1, cnt);//最后一个数交换到第一个数
//通过数组下标--,起到删除尾结点的作用
cnt--;
//保持堆的特性
down(1);
}
//删除第k个插入的数
if (op == "D") {
cin >> k;
k = ph[k];//第k个插入的数，在堆里的位置
//和最后一个元素交换一下
heap_swap(k, cnt);
//删除
cnt--;
//最后一个元素换到k原来的位置，可能需要调整，调整都是无脑的up,down
down(k);
up(k);
}
//将第k个插入的数修改
if (op == "C") {
cin >> k >> x;
k = ph[k];//取出在堆中的位置
h[k] = x; //修改堆中对应的值
down(k);
up(k);
}
}
return 0;
}
二、STL堆的实现
#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
int a[N], cnt;
multiset<int> s;
int n;
string t;
int x, k;
int main() {
//读入优化
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> t;
if (t == "I") {//插入一个数
cin >> x;
s.insert(x);
//记录第几个是什么数
a[++cnt] = x;
}
//输出当前集合中的最小值
if (t == "PM") cout << *s.begin() << endl;
//删除当前集合中的最小值
//*s.begin()是堆顶值，即最小值
if (t == "DM")
//下面这句话的作用就是利用find找出堆顶的迭代器，然后利用s.erase进行删除
s.erase(s.find(*s.begin()));
//删除第k个插入的数
if (t == "D") {
cin >> x;
if (s.find(a[x]) != s.end())
s.erase(s.find(a[x]));
}
//修改第k个插入的数，将其变为x；
if (t == "C") {
cin >> k >> x;
if (s.find(a[k]) != s.end()) s.erase(s.find(a[k]));
a[k] = x;
s.insert(x);
}
}
return 0;
}