题目描述
维护一个集合,初始时集合为空,支持如下几种操作:
I x,插入一个数 x;
PM,输出当前集合中的最小值;
DM,删除当前集合中的最小值(数据保证此时的最小值唯一);
D k,删除第 k 个插入的数;
C k x,修改第 k 个插入的数,将其变为 x;
现在要进行 N 次操作,对于所有第 2 个操作,输出当前集合的最小值。
输入格式
第一行包含整数 N。
接下来 N 行,每行包含一个操作指令,操作指令为 I x,PM,DM,D k 或 C k x 中的一种。
输出格式
对于每个输出指令 PM,输出一个结果,表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤1e5
−109≤x≤1e9
数据保证合法。
输入样例:
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例:
-10
6
hp、ph
hp是heap pointer的缩写,表示堆数组中下标到第k个插入的映射
ph是pointer heap的缩写,表示第k个插入到堆数组中的下标的映射
hp和ph数组是互为反函数的。
注意:
在堆这个数据结构中,数据的插入都是插入到堆尾,然后再up。
但是为什么会用ph和hp这两个数组呢?
原因在于在删除第k个插入元素的操作中,我们首先得知道第k个插入元素在堆数组中的什么位置,即堆数组下标。
很显然,用一个ph数组来存储会方便查找。这样我们就知道了第k个插入的元素在哪了。
然后我们需要做的是和堆尾元素交换,最后再在原来第k个元素所在的位置进行down和up操作。
由于交换完后ph[k]的值变了,为ph[size]了,所以必须要在之前保存ph[k]的值,不然无法进行down和up操作。
似乎有了ph数组就可以完成所有操作了,但为什么还要有一个hp数组呢?
原因就在于在swap操作中我们输入是堆数组的下标,无法知道每个堆数组的下标对应的是第几个插入的元素。
所以需要hp数组方便查找。
算法1
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int h[N]; //堆
int ph[N]; //存放第k个插入点在堆中的下标
int hp[N]; //存放堆中点的插入次序(即堆中某点是第几个插入的点)
int cur_size; //size 记录的是堆当前的数据多少
//这个交换过程关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
//之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序
//从而我们需要对应到原先第K个堆中元素
//如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换
//h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响
void heap_swap(int u,int v)
{
swap(h[u],h[v]);
swap(hp[u],hp[v]);
swap(ph[hp[u]],ph[hp[v]]);
}
void down(int u)
{
int t=u;
if(u*2<=cur_size&&h[t]>h[u*2]) t=u*2;
if(u*2+1<=cur_size&&h[t]>h[u*2+1]) t=u*2+1;
if(u!=t)
{
heap_swap(u,t);
down(t);
}
}
void up(int u)
{
if(u/2>0&&h[u]<h[u/2])
{
heap_swap(u,u/2);
up(u>>1);
}
}
int main()
{
int n;
cin>>n;
int m=0; //m用来记录插入的数的个数
//注意m的意义与cur_size是不同的 cur_size是记录堆中当前数据的多少
//对应上文 m即是hp中应该存的值
while(n--)
{
string op;
int k,x;
cin>>op;
if(op=="I")
{
cin>>x;
m++;//记录第几次插入
h[++cur_size]=x;//记录插入的值
ph[m]=cur_size,hp[cur_size]=m;//每次插入都是在堆尾插入
up(cur_size);
}
else if(op=="PM") cout<<h[1]<<endl;
else if(op=="DM")
{
heap_swap(1,cur_size);
cur_size--;
down(1);
}
else if(op=="D")
{
cin>>k;
int u=ph[k]; //这里一定要用u=ph[k]保存第k个插入点的下标//必须要保存当前被删除结点的位置
heap_swap(u,cur_size);//因为在此处heap_swap操作后ph[k]的值已经发生
//第k个插入的元素移到了堆尾,此时ph[k]指向堆尾
cur_size--; //删除堆尾
up(u); //u是之前记录被删除的结点的位置//如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
down(u);
}
else if(op=="C")
{
cin>>k>>x;
h[ph[k]]=x; //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个
down(ph[k]); //所以可直接传入ph[k]作为参数
up(ph[k]);
}
}
return 0;
}
算法2