巨弱询问堆
查看原帖
巨弱询问堆
241817
Chancylaser楼主2021/3/5 20:18

全RE,大佬能康一下怎么回事吗:

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int h[1005];
int n;
int l;
int num;
void swapp(int x,int y){//交换 
	int t;
	t=h[x];
	h[x]=h[y];
	h[y]=t;
	return;
}
void siftdown(int i){//向下调整 
	int t,flag=0;
	while(i*2<=n&&flag==0){
		if(h[i]>h[i*2]){
			t=i*2;
		}
		else t=i;
		if(i*2+1<=n){
			if(h[t]>h[i*2+1])
				t=i*2+1;
		}
		if(t!=i){
			swapp(t,i);
			i=t;
		}
		else 
			flag=1;
	}
	return;
}
void siftup(int i){//向上调整 
	int flag=0;
	if(i==1) return;
	while(i!=1&&flag==0){
		if(h[i]<h[i/2]){
			swapp(i,i/2);
		}
		else 
			flag=1;
		i=i/2;
	}
	return;
}
void creat(){//建树 
	int i;
	for(i=n/2;i>=1;i--){
		siftdown(i);
	}
	return;
}
int deletemin(){//询问最小值 
	int t;
	t=h[1];
	h[1]=h[n];
	n--;
	siftdown(1);
	return t;
}
int main(){
	cin>>n;
	int qwq=n;
	creat();
	while(qwq--){
		cin>>l;
		if(l==1){
			cin>>num;
			siftup(num);
		}
		if(l==2){
			cout<<h[1]<<"\n";
		}
		if(l==3){
			deletemin();
		}
	}
	return 0; 
}
2021/3/5 20:18
加载中...