思考
要理解堆中的映射关系,就需要理解实际上ph和hp保存了什么
ph[m] = i表示第m个插入的元素在堆中的下标为i,因此需要用一个m来记录当前存入的是第几个插入的元素,所以在做插入操作时,不仅要修改堆h, 还需要记录当前第m个插入的元素ph[m] = cnt;(cnt表示的是堆中的最后一个元素)
if (op == "I")
{
......
cnt++ ;
m ++ ; //插入第m个数
ph[m] = cnt; //第m个插入的数在堆的末尾
......
}
那为什么又要又hp这个数组呢?这时,如果我们想从堆中下标为i的元素找到他是第几个插入的,只有上面的ph是无法实现的,所以这时需要额外再维护一个hp数组,因此这个数组的含义就很明显了,hp[i] = k表示的是,堆中下标为i的元素是第k个插入的,所以代码写成了这样
if (op == "I")
{
......
cnt++ ;
m ++ ; //插入第m个数
ph[m] = cnt; //第m个插入的数在堆的末尾
hp[cnt] = m; //在堆中下标为cnt的元素是第m个插入的
//显然ph和hp互为逆运算
.....
}
基于以上分析,交换操作的含义就更加明确了,如果要交换堆中的下标u和v的元素,我们需要交换三个位置
1. 交换ph数组,这时需要先根据hp[u]来找到堆中下标为u的元素在ph中的下标,最后交换这两值
2. 交换hp数组,ph交换了hp也必然要交换,否则两者就不互为逆运算了
3. 最后交换堆中的元素
void heap_swap(int u, int v) {
swap(hp[ph[u]], hp[ph[v]]);
swap(ph[u], ph[v]);
swap(h[u], h[v]);
}
完整代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5+5;
int n;
int hp[N], ph[N], h[N], cnt, m;
void heap_swap(int u, int v) {
swap(ph[hp[u]], ph[hp[v]]);
swap(hp[u], hp[v]);
swap(h[u], h[v]);
}
void down(int u){
int t = u;
if(2*u <= cnt && h[2*u] < h[t]) t = 2*u;
if(2*u + 1 <= cnt && h[2*u + 1] < h[t]) t = 2*u + 1;
if(u != t){
heap_swap(t, u);
down(t);
}
}
void up(int u){
while(u > 1 && h[u] < h[u/2]){
heap_swap(u, u/2);
u /= 2;
}
}
int main(){
scanf("%d",&n);
while(n--) {
char op[3];
int k, x;
scanf("%s", op);
if(*op == 'I') {
scanf("%d", &x);
cnt++;
m++; //当前元素为第m个插入的元素
hp[cnt] = m; //下标为cnt的元素是第m个插入的元素
ph[m] = cnt; //第m个插入的元素在堆中的下标为cnt
h[cnt] = x; //值为x
up(cnt);
}
else if(!strcmp(op, "PM")) { //输出堆中的最小值
printf("%d\n", h[1]);
}
else if(!strcmp(op, "DM")) { //删除堆中元素的最小值
heap_swap(1, cnt--);
down(1);
}
else if(!strcmp(op, "D")) { //删除第k个插入的元素
scanf("%d", &k);
k = ph[k]; //根据ph数组找到第k个插入的元素在堆中的位置,重新赋值给k
heap_swap(k, cnt--); //先把第k个数换到末尾
down(k), up(k); //调整堆
}
else { //修改第k个插入的数
scanf("%d%d", &k, &x);
k = ph[k]; //同上
h[k] = x; //修改值
down(k), up(k); //调整堆
}
}
return 0;
}