这道题自己想起来还是比较绕,尤其是heap_swap()
这个函数里的操作,试着写一下自己的理解吧。
这个题要维护每个数的插入顺序,所以用了ph[]
和hp[]
两个数组,假设是第k
个插入的数,它在堆中的下标是size
,那么ph[k] = size; hp[size] = k;
。即ph[]
能将第k
个插入的数直接映射到它在堆中的位置,而hp[]
可以求得堆中某一位置上存放的是哪次插入的数。
现在考虑要交换堆中的两个数3
和5
,其中3
是第k
个插入的数,在堆中的位置是size
, 5
是第m
个插入的数,在堆中的位置是size/2
.即hp[size] = k, ph[k] = size; hp[size/2]=m, ph[m] = size;
我们要交换3
和5
,不仅要交换这两个值,还要让他们的插入顺序这一信息跟着变动(如果不交换各自的插入顺序,那么5
就变成第k
个,3
变成第m
个)。那么,交换之后的结果应该是在堆中位置size
存放5
,且hp[size] = m,ph[m] = size;
同样在堆中位置size/2
存放的是3
,且hp[size/2] = k, ph[k] = size/2;
可以看到hp[]
, ph[]
数组的值都要相互交换,于是就有了heap_swap()
函数里面的操作:
void heap_swap(int a, int b){
swap(ph[hp[a]], ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
感觉说到这里也没有把这个过程说得太明白,但把交换前后哪些东西要发生改变写出来,就大致能明白上面这个代码在做什么。最后是完整代码:
#include <iostream>
#include <string>
using namespace std;
const int N = 1e5 + 10;
int h[N], hp[N], ph[N], size = 0;
void heap_swap(int a, int b){
swap(ph[hp[a]], ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void up(int u){
while(u/2 && h[u/2] > h[u]){
heap_swap(u/2, u);
u /= 2;
}
}
void down(int u){
int t = u;
if(u*2 <= size && h[u*2]<h[t]) t = u*2;
if(u*2+1 <= size && h[u*2+1] < h[t]) t = u*2+1;
if(u != t){ heap_swap(u, t); down(t);}
}
int main(){
int n; scanf("%d", &n);
int idx = 1; //第idx个插入的数
while(n--){
string op; cin >> op;
if(op == "I"){
int x; scanf("%d", &x);
h[++size] = x;
hp[size] = idx;
ph[idx] = size;
idx++;
up(size);
}else if(op == "PM"){
printf("%d\n", h[1]);
}else if(op == "DM"){
heap_swap(1, size); size--; down(1);
}else if(op == "D"){
int k; scanf("%d", &k);
k = ph[k]; //第k个插入的数实际在堆当中的位置
heap_swap(k, size); size--; down(k); up(k);
}else{
int k, x; scanf("%d%d", &k,&x);
k = ph[k];
h[k] = x; down(k); up(k);
}
}
return 0;
}