定义

堆，是一棵树，且每个节点的键值都大于等于 / 小于其父亲的键值。

左偏树是一种可合并的堆，可以以 $O(\log n)$ 的复杂度实现合并。

性质

左偏树满足堆的性质。

我们设定一个值 $\text{dist}$，定义外节点为左儿子或右儿子为空的节点。

外节点的 $\text{dist}$ 为 $1$。非外节点的 $\text{dist}$ 为它到它子树中最近的外节点的距离加 $1$。空节点 $\text{dis}=0$。

每个节点左儿子的 $\text{dist}$ 大于右儿子的，左偏树中每个节点的 $\text{dist}$ 都等于它右儿子的 $\text{dist}$ 加 $1$。

操作

• 合并两个堆
• 插入节点
• 删除最小 / 大值（根）

实现

可以用 pb_ds 库实现。注意要加上以下两行：

#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;

Portal.

以下代码实现的是合并和删除根节点操作。

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;struct node
{int id,v;bool friend operator < (node a,node b){if(a.v!=b.v) return a.v>b.v;return a.id>b.id;}
};
const int maxn=1e5+5;
__gnu_pbds::priority_queue<node> q[maxn];
int fa[maxn];
bool vis[maxn];int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}int main()
{int n,m;cin>>n>>m;for(int i=1,tmp;i<=n;i++) cin>>tmp,q[i].push((node){i,tmp}),fa[i]=i;for(int op,i=1;i<=m;i++){cin>>op;if(op==1){int x,y;cin>>x>>y;int fx=find(x),fy=find(y);if(fx==fy||vis[x]||vis[y]) continue;fa[fx]=fy,q[fy].join(q[fx]);}else{int x;cin>>x;if(vis[x]) {cout<<"-1\n";continue;}else cout<<q[find(x)].top().v<<'\n',vis[q[find(x)].top().id]=1,q[find(x)].pop();}}return 0;
}