二叉堆求帮忙
查看原帖
二叉堆求帮忙
502225
蒟蒻JJA༙楼主2021/4/10 14:57

样例过不去

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
//#include<map>
#include<vector>
#include<math.h>
using namespace std;
//#define int long long
#define forr(i,a,b) for(int i=a;i<=b;i++)
#define repp(i,a,b) for(int i=a;i>=b;i--)
#define INF 1e9
#define ll long long
#define MAXN 200005
const int _x[]={0,1,0,-1,0},_y[]={0,0,1,0,-1};
#define mem(a,n) memset(a,n,sizeof(a));
#define chkmax(a,b) a=a>b?a:b;
#define chkmin(a,b) a=a<b?a:b;
#include<set>
#include<stack>
int heap[MAXN*5];
int size;
void insert(int i,int x){
	heap[i]=x;
	int now=size;
	if(heap[i>>1]>x){
		heap[i]=heap[i>>1];
		insert(i>>1,x);
	}
}
void pop(int i,int x){
	heap[i]=x;
	if((i<<1)<=size&&x>heap[i<<1]||x>heap[(i<<1)|1]){
		heap[i]=heap[i<<1]<heap[(i<<1)|1]?heap[i<<1]:heap[(i<<1)|1];
		pop(heap[i<<1]<heap[(i<<1)|1]?i<<1:i<<1|1,x);
	}
}
int n;
int main(){
	scanf("%d",&n);
	forr(i,1,n){
		int opt,x;
		scanf("%d",&opt);
		if(opt==1){
			scanf("%d",&x);
			insert(++size,x);
		}
		else if(opt==2){
			printf("%d\n",heap[1]);
		}
		else{
			pop(1,heap[size]);
			--size;
		}
	}
}
2021/4/10 14:57
加载中...