题目描述
维护一个集合,初始时集合为空,支持如下几种操作:
1. I x,插入一个数 x;
2. PM,输出当前集合中的最小值;
3. DM,删除当前集合中的最小值(数据保证此时的最小值唯一);
4. D k,删除第 k 个插入的数;
5. C k x,修改第 k 个插入的数,将其变为 x;
现在要进行 N 次操作,对于所有第 2 个操作,输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行,每行包含一个操作指令,操作指令为 I x,PM,DM,D k 或 C k x 中的一种。
输出格式
对于每个输出指令 PM,输出一个结果,表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤105
−109≤x≤109
数据保证合法。
输入样例
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例
-10
6
先来理解hp[N] ph[N] 两个映射指针
完整c++代码(详解版)—AC
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int h[N],hp[N],ph[N]; // hp 表示堆的下标映射到第k个插入的点 也就是左指针 ph 表示第i插入映射到堆里的坐标 右指针
int n,idx=0,mysize=0; // idx 用来记录插入了几个数 mysize 是集合大小
// 交换操作 交换数值的同时交换它们的映射
void myswap(int a,int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
// 下调操作
void down(int u)
{
int t=u;
if(2*u<=mysize && h[2*u]<h[t]) t=2*u;
if(2*u+1<=mysize && h[2*u+1]<h[t]) t=2*u+1;
if(u!=t)
{
myswap(u,t);
down(t);
}
}
// 上调操作
void up(int u)
{
while(u/2 && h[u/2]>h[u])
{
myswap(u/2,u);
u/=2;
}
}
int main()
{
cin >> n;
while(n--)
{
string op;
int k,x;
cin >> op;
// I 对应插入 x 插入的同时记得初始化它的两个左右指针 也就是映射 方便记录是第几个插入的数
if(op=="I")
{
cin >> x;
idx++;
mysize++;
h[mysize]=x;
hp[mysize]=idx;// 表示堆数组中下标为 i (mysize) 的元素是第 j(idx) 个插入的
ph[idx]=mysize; // 表示第 i 个插入的数在堆数组中下标为 j
up(mysize);
}
// PM 对应输出最小值 也就是堆顶
else if(op=="PM")
{
cout << h[1] << endl;
}
// DM 对应删除最小值 也就是堆顶
else if(op=="DM")
{
// 首先应该先用最后一个数将堆顶覆盖掉 然后size-- 但是修改值的同时应该考虑到映射指针
// 所以不妨直接用我们的 mysize 操作 覆盖的同时也能修改映射指针
myswap(1,mysize);
mysize--;
down(1);
}
// D 对应删除 第k个插入的数
else if(op=="D")
{
cin >> k;
// 1.0 首先应该知道第k个插入的数在堆中对应的下标是多少 那么就会用到我们的ph[]
k=ph[k]; // k 此时的值就是我们想要的坐标
// 2.0 知道了需要删除的数的坐标 那么接下来就很简单了
myswap(k,mysize); // 用最后一个数覆盖掉第k个插入的数
mysize--;
down(k),up(k); // 将调整后的数调整到正确的位置
}
// C 对应修改第k个插入的数为x
else if(op=="C")
{
cin >> k >> x;
// 1.0 首先也是应该先知道第k个插入的数在堆中对应的下标是多少 和"D"操作第一步一样
k=ph[k];
// 2.0 然后开始操作
h[k]=x; // 修改完成
up(k),down(k); // 调整到合适位置
}
}
return 0;
}