问:为什么down用了递归,up用循环
答:我的理解,down函数内部有2个判断分支,不好用循环处理。而up只有一个分支,循环处理的很方便。这也是循环和递归的一大区别,循环只能处理简单的循环节,如果复杂版的循环都要用递归,比较方便。
2处错误。
1、up函数的swap写成swap(u,u/2)
了,交换的是数组的值,不是下标,所以出错了,应该写成swap(h[u],h[u/2])
2、删除最小值时,忘记把总数cnt减减了。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int n;
int h[N],cnt;
void down(int u){
int t=u;
if(u*2<=cnt&&h[u*2]<h[t]) t=u*2;
if(u*2+1<=cnt&&h[u*2+1]<h[t]) t=u*2+1;
if(u!=t){
swap(h[u],h[t]);
down(t);
}
}
void up(int u){
while(u/2&&h[u]<h[u/2]){
swap(h[u],h[u/2]);//这里一开始写错成swap(u,u/2)
u/=2;
}
}
int main(){
scanf("%d",&n);
while(n--){
int op,x;
scanf("%d",&op);
if(op==1){
scanf("%d",&x);
h[++cnt]=x;
up(cnt);
}
else if(op==2){
printf("%d\n",h[1]);
}
else if(op==3){
h[1]=h[cnt--];//这里一开始忘记减减了,删掉一个要减一下总数。
down(1);
}
}
return 0;
}