C16【模板】左偏树（可并堆）

C16站内下载

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=1e5+10;
int v[N],lc[N],rc[N],dis[N]; //左偏树
int fa[N]; //并查集

int find(int x){ //并查集找根
  return x==fa[x] ? x : fa[x]=find(fa[x]);
}
int merge(int x,int y){
  if(!x||!y) return x+y; //若一个堆为空则返回另一个堆
  if(v[x]==v[y] ? x>y : v[x]>v[y]) swap(x,y); //取小值做根
  rc[x]=merge(rc[x],y); //递归合并右儿子与另一个堆
  
  if(dis[lc[x]]<dis[rc[x]]) swap(lc[x],rc[x]); //维护左偏性
  dis[x]=dis[rc[x]]+1;  //更新dis
  return x; //返回合并后的根
}
int main(){
  int n,m; scanf("%d%d",&n,&m);
  for(int i=1; i<=n; i++) scanf("%d",&v[i]);
  for(int i=1; i<=n; i++) fa[i]=i;
  dis[0]=-1; //空节点的dis初始化
  for(int op,x,y; m; m--){
    scanf("%d",&op);
    if(op==1){ //合并堆
      scanf("%d%d",&x,&y);
      if(v[x]==-1 || v[y]==-1) continue;
      x=find(x), y=find(y);
      if(x!=y) fa[x]=fa[y]=merge(x,y);
    }
    else{ //删除堆顶
      scanf("%d",&x);
      if(v[x]==-1){printf("-1\n"); continue;}
      x=find(x);
      printf("%d\n",v[x]);
      v[x]=-1; //删除标记
      fa[lc[x]]=fa[rc[x]]=fa[x]=merge(lc[x],rc[x]);
    }
  }
}

STL(代码已更新20250904 10：48)

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define pii pair<int,int>
#define ft first
#define sd second
priority_queue<pii,vector<pii>,greater<pii>> Q[N];
int fa[N],del[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y)
{
	if(del[x] || del[y]) return;
	int fx=find(x),fy=find(y);
	if(fx==fy) return;
	if(Q[fx].size()<Q[fy].size())swap(fx,fy);
	fa[fy]=fx;
	while(!Q[fy].empty())
	{
		Q[fx].push(Q[fy].top());
		Q[fy].pop();
	}
}
int query(int x)
{
	if(del[x]) return -1;
	int fx=find(x); 
	pii ans=Q[fx].top(); Q[fx].pop();
	del[ans.sd]=1;
	return ans.ft;
}
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	for(int i=1,x;i<=n;i++)
	{
		scanf("%d",&x);
		Q[i].push({x,i});
		fa[i]=i,del[i]=0;
	}
	int op,x,y;
	while(m--)
	{
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d%d",&x,&y);
			merge(x,y);
		}
		if(op==2)
		{
			scanf("%d",&x);
			printf("%d\n",query(x));
		}
	}
	return 0;
}

pbds （不推荐）

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
const int N=1e5+10;
#define pii pair<int,int>
#define ft first
#define sd second
__gnu_pbds::priority_queue<pii,greater<pii>> Q[N];
int fa[N],del[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x,int y)
{
    if(del[x] || del[y]) return;
    int fx=find(x),fy=find(y);
    if(fx==fy) return;
    if(Q[fx].size()<Q[fy].size())swap(fx,fy);
    fa[fy]=fx;
    Q[fx].join(Q[fy]);
}
int query(int x)
{
    if(del[x]) return -1;
    int fx=find(x); 
    pii ans=Q[fx].top(); Q[fx].pop();
    del[ans.sd]=1;
    return ans.ft;
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1,x;i<=n;i++)
    {
        scanf("%d",&x);
        Q[i].push({x,i});
        fa[i]=i,del[i]=0;
    }
    int op,x,y;
    while(m--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d",&x,&y);
            merge(x,y);
        }
        if(op==2)
        {
            scanf("%d",&x);
            printf("%d\n",query(x));
        }
    }
    return 0;
}