模拟堆的原理虽然挺简单 但有很多需要注意的细节
要写完全写对 还应该把映射关系理清楚才行
感谢评论区同学的提醒 由于编译器更新的原因 size已经是关键字 已经将size 均修改为cur_size
#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;
//down(size);
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]的值已经发生
cur_size--; //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
up(u);
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;
}
换个角度理解,因为堆的插入或者down和up操作都是基于下标来的,所以奠定了交换不能动下标,只能交换值而不能整体交换的前提。所以如果带上第k个的属性,那么就要另辟数组对应来存储了。
D操作里不应该是用u来存ph[k]然后heap_swap[ph[k],cur_size]吗?如果还是用heap_swap[u,cur_size]那u的值不是也被改变了吗?
服务器的编译器更新了,size变成了关键字,建议换一个名字Hh
好滴 感谢提醒 已经修改了
我觉得之所以修改操作可以直接传入ph[k]是因为,这里的up和down是确定的数的下标。因为每一个堆中数组的k是一对一的映射。所以ph[k]就是找到的确定的数字。但是删除操作是要确定的下标的。因为ph[k]在swap中指向了size的位置,所以ph[k]中丢失了原先的下标。这样swap前后中ph[k]的值就不一样,但删除操作是对swap前那个确定的下标做up和down,所以需要提前保存
值,节点,下标都要换
为什么up函数里最后不用递归down(u)
可以改为递归,也可以循环
为什么在 D 操作哪里,我把
int u = ph[k] 省略掉,u的地方全用ph[k]就不行?
有可能在交换的过程中,ph[k]被改变了,到下面函数就不是此时的phk了
phk交换后改变了,你要用u来保存未改变之前的值
因为传入的u,v是堆h的下标而不是代表第几个插入,但是ph的下标代表第几个插入,所以要转换成第几个插入的就要hp[u],hp[v];
把这个理解了其实交换那里不绕了
感谢!
感谢
想了半天hp在这道题里的作用,结果是没有用到。
作用在swap的函数里面
为什么在op等于”D”的时候要先up(u)啊
这和删除的操作方式有关
删除操作的步骤是将 该位置的数与最后一个位置的数交换
但无法确定交换之后 在该位置的数是变小了 还是变大了 所以索性up 一遍 down一遍
谢谢
堆的定义是每一个节点都比其父节点大或小 但最后一个节点不一定是最大或最小 这个可以随便画个例子感受一下....
他這個堆定义的不是 父节点小于左右子节点吗 位于最后一个数不就应该是最大的数吗
嗷嗷好的
这里直接用一个h数组不行吗?
为啥要用三个数组,有点搞不懂了
不行 因为这是和题意有关的
4.“D k”,删除第k个插入的数;y.“C k x”,修改第k个插入的数,将其变为x;
但是经过一系列之前的1,2,3操作已经堆排序的过程 只用一个h数组就无法找到原来插入的第k个数了 所以需要添加一个数组建立映射 再添加一个数组存储原来第k个数的值
噢噢,懂了 Orz
赞一个hh