社区讨论

为什么我的小根堆和set都去世了.....

P3378【模板】堆参与者 8已保存回复 13

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
13 条
当前快照
1 份
快照标识符
@mi7yise5
此快照首次捕获于
2025/11/21 05:42
4 个月前
此快照最后确认于
2025/11/21 06:44
4 个月前
查看原帖
这是手打的小根堆...
CPP
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

int num=0;
int heap[10000001];

void insert(int x)
{
	heap[++num]=x;
	int fa=num;
	while(fa>1)
	{
		int root=fa/2;
		if(heap[root]>x)
		{
			swap(heap[root],heap[fa]);
		}
		else break;
		fa=root;
	}
}

void pop()
{
	if(num==0) return;
	int top=heap[1];
	heap[1]=heap[num];num--;
	int root=1;
	while(2*root<num)
	{
		int l=2*root;
		int r=2*root+1;
		if(heap[root]>heap[l])
		{
			swap(heap[root],heap[l]);
			root=l;
		}
		else if(heap[root]>heap[r])
		{
			swap(heap[root],heap[r]);
			root=r;
		}
	}
	
}

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int flag;
		scanf("%d",&flag);
		if(flag==1)
		{
			int x;
			cin>>x;
			insert(x);
		}
		if(flag==2)
		{
			cout<<heap[1]<<endl;
		}
		if(flag==3)
		{
			pop();
		}
	}
}
这是set....
CPP
#include<set>
#include<iostream>
#include<cstring>
using namespace std;



int main()
{
	set<int> s;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int flag;
		cin>>flag;
		if(flag==1)
		{
			int x;
			cin>>x;
			s.insert(x);
		}
		if(flag==2)
		{
			 cout<<*s.begin()<<endl;
		}
		if(flag==3)
		{
			s.erase(s.begin());
		}
	}
}

回复

13 条回复,欢迎继续交流。

正在加载回复...