一日一题：第十一题---模拟堆（很认真！）

​作者：小妮无语
专栏：一日一题

🚶‍♀️✌️道阻且长，不要放弃✌️🏃‍♀️

哭了，一定要记录，为了，写这篇文章千辛万苦

 堆笔记

题目描述：

 维护一个集合，初始时集合为空，支持如下几种操作：

“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≤105
−10^9≤x≤10^9
数据保证合法

输入样例：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例：

-10
6

代码:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int dz[N],d[N],h[N],cnt,idx;
// dz[cnt]=idx;
// d[idx]=cnt;
char s[5];
void h_swap(int a,int b)
{swap(d[dz[a]],d[dz[b]]);swap(dz[a],dz[b]);swap(h[a],h[b]);
}
void up(int a)
{while(a/2&&h[a]<h[a/2]){h_swap(a,a/2);a=a>>1;}
}
void down(int a)
{int u=a;if(a*2<=cnt &&h[a*2]<h[a]) u=a*2;if(a*2+1<=cnt&&h[a*2+1]<h[a]) u=a*2+1;if(a!=u){h_swap(a,u);down(u);}
}
int main()
{int n;cin>>n;while(n--){cin>>s;int k,x;if(!strcmp(s,"I")){cin>>x;cnt++;idx++;h[cnt]=x;dz[cnt]=idx;d[idx]=cnt;up(cnt);}else if(!strcmp(s,"PM")){cout<<h[1]<<endl;}else if(!strcmp(s,"DM")){h_swap(1,cnt);cnt--;down(1);}else if(!strcmp(s,"D")){cin>>k;k=d[k];h_swap(k,cnt);cnt--;down(k),up(k);}else if(!strcmp(s,"C")){cin>>k>>x;k=d[k];h[k]=x;down(k),up(k);}}return 0;
}

想具体说说我出现的问题：

1. 写着写着映射关系忘了

      dz是根据位置找第几个插入的

      d是根据第几个插入的找地址

2. 我的h_swap(),传过去的参数是地址，而不是第几个插入的数，所以在交换时，要根据地址找第几个插入的数来进行交换--d[dz[a]]

3. 我们输入的是第K个数怎么怎么，但是我们的"h[ ]"数组里对应的下标是地址的编号，所以我们先进来把k换为dz[k]

4. strcmp(字符串a,字符串b)，如果a=b，呢么返回"0"!!

             == 欢迎来到一日一题的小菜鸟频道，睡不着就看看吧！==

 

                         ==  跟着小张刷题吧！==