自动搬运

查看原文

来自洛谷，原作者为

	hsfzLZH1 我永远喜欢珂朵莉

搬运于2025-08-24 21:48:19，当前版本为作者最后更新于2019-07-10 17:25:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

左偏树是 一种 支持在 $O(\log_2 n)$ 的时间复杂度内进行合并的 堆式 数据结构。

一些定义

外结点 ：左儿子或右儿子是空结点的结点。

距离 ： 一个结点 $x$ 的距离 $dist_x$ 定义为其子树中与结点 $x$ 最近的外结点到 $x$ 的距离。特别地，定义空结点的距离为 $-1$ 。

左偏树的基本性质

左偏树具有 堆性质 ，即若其满足小根堆的性质，则对于每个结点 $x$ ，有 $v_x\le v_{lc},v_x\le v_{rc}$ 。

左偏树具有 左偏性质 ，即对于每个结点 $x$ ,有 $dist_{lc}\ge dist_{rc}$ 。

基本结论

1. 结点 $x$ 的距离 $dist_x=dist_{rc}+1$ 。

2. 距离为 $n$ 的左偏树至少有 $2^{n+1}-1$ 个结点。此时该左偏树的形态是一棵满二叉树。

3. 有 $n$ 的结点的左偏树的根节点的距离是 $O(\log_2 n)$ 的。

基本操作：合并操作

左偏树最基本的操作是合并操作。

定义 merge(x,y) 为合并两棵分别以 $x,y$ 为根节点的左偏树，其返回值为合并之后的根节点。

首先不考虑左偏性质，我们描述一下合并两个具有堆性质的树的过程。假设我们要合并的是小根堆。

1. 若 $v_x\le v_y$ ，以 $x$ 作为合并后的根节点；否则以 $y$ 作为合并后的根节点。为避免讨论，若有 $v_x>v_y$ ，交换 $x,y$ 。

2. 将 $y$ 与 $x$ 的其中一个儿子合并，用合并后的根节点代替与 $y$ 合并的儿子的位置，并返回 $x$ 。

3. 重复以上操作，如果 $x$ 和 $y$ 中有一个为空节点，返回 $x+y$ 。

令 $h$ 为树高， $h_x+h_y$ 每次都减少了 $1$ ，上述过程的时间复杂度是 $O(h)$ 的，当合并的树退化为一条链时，这样做的复杂度是 $O(n)$ 的。要使时间复杂度更优，就要使树合并得更 平衡 。我们有两种方式：

1. 每次随机选择 $x$ 的左右儿子进行合并。（有没有感觉这很像 FHQ Treap ？）

2. 左偏树。

由于左偏树中左儿子的距离大于右儿子的距离，我们 每次将 $y$ 与 $x$ 的右儿子合并 。由于左偏树的树高是 $O(\log_2 n)$ 的，所以单次合并的时间复杂度也是 $O(\log_2 n)$ 的。

但是，两棵左偏树按照上述方法合并后，可能不再保持左偏树的左偏性质。在每次合并完之后，判断对结点 $x$ 是否有 $dist_{lc}\ge dist_{rc}$ ，若没有则交换 $lc,rc$ ，并维护 $x$ 的距离 $dist_x=dist_{rc}+1$ ，即可维护左偏树的左偏性质。

由于合并后的树既满足堆性质又满足左偏性质，所以合并后的树仍然是左偏树。

int merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(v[y]<v[x])swap(x,y);
    rc[x]=merge(rc[x],y);
    if(dist[lc[x]]<dist[rc[x]])swap(lc[x],rc[x]);
    dist[x]=dist[rc[x]]+1;
    return x;
}

左偏树的其他基本操作

插入给定值

新建一个值等于插入值的结点，将该节点与左偏树合并即可。时间复杂度 $O(\log_2 n)$ 。

求最小值

由于左偏树的堆性质，左偏树上的最小值为其根节点的值。

删除最小值

等价于删除左偏树的根节点。合并根节点的左右儿子即可。记得维护已删除结点的信息。

给定一个结点，求其所在左偏树的根节点

我们可以记录每个结点的父亲结点 $fa_i$ ，然后暴力跳父亲结点。

int findrt(int x)
{
    if(fa[x])return findrt(fa[x]);
    return x;
}

注意，虽然左偏树的距离是 $O(\log_2 n)$ 的，但是左偏树的深度最大可以是 $O(n)$ 的，这种做法的复杂度也是 $O(n)$ 的。

上面的代码让你想到了什么？并查集。我们同样可以用 路径压缩 的方式，求一个结点所在左偏树的根节点。

int find(int x){return rt[x]==x?x:rt[x]=find(rt[x]);}

使用这种写法，需要维护 rt[x] 的值。

在合并两个结点 $x,y$ 时，令 rt[x]=rt[y]=merge(x,y) 。

在删除左偏树中的最小值时，令 rt[lc[x]]=rt[rc[x]]=rt[x]=merge(lc[x],rc[x]) ，因为 $x$ 是之前左偏树的根节点，在路径压缩时可能有 rt 的值等于 $x$ ，所以 rt[x] 也要指向删除后的根节点。

由于 $x$ 已经被作为中间量使用得不成样子，如果之后还要用到结点 $x$ ，需要新建一个值相同的结点。

路径压缩后，可以在 $O(\log_2 n)$ 的优秀时间复杂度内找到一个点所在左偏树的根节点。

代码展示

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
int n,m,op,x,y;
int lc[maxn],rc[maxn],dist[maxn],rt[maxn];
bool tf[maxn];
struct node
{
    int id,v;
    bool operator<(node x)const{return v==x.v?id<x.id:v<x.v;}
}v[maxn];
int find(int x){return rt[x]==x?x:rt[x]=find(rt[x]);}
int merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(v[y]<v[x])swap(x,y);
    rc[x]=merge(rc[x],y);
    if(dist[lc[x]]<dist[rc[x]])swap(lc[x],rc[x]);
    dist[x]=dist[rc[x]]+1;
    return x;
}
int main()
{
    dist[0]=-1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&v[i].v),rt[i]=i,v[i].id=i;
    while(m--)
    {
        scanf("%d%d",&op,&x);
        if(op==1)
        {
            scanf("%d",&y);
            if(tf[x]||tf[y])continue;
            x=find(x);y=find(y);
            if(x!=y)rt[x]=rt[y]=merge(x,y);
        }
        if(op==2)
        {
            if(tf[x]){printf("-1\n");continue;}
            x=find(x);
            printf("%d\n",v[x].v);
            tf[x]=true;
            rt[lc[x]]=rt[rc[x]]=rt[x]=merge(lc[x],rc[x]);
            lc[x]=rc[x]=dist[x]=0;
        }
    }
    return 0;
}