左偏树详解-CSDN博客

本文链接：https://blog.csdn.net/hacker__man/article/details/119103714

写在前边：为什么突然想学习左偏树了呢？答：写蓝书线性dp分级的时候，想知道如果需要打印的话不清楚怎么写，然后发现进阶课中的数字序列好像就是这种题型，还有一点就是LICS打印也不会，学通左偏树，废话不多说了

左偏树

重要的性质：

以左偏树维护小根堆为例，左偏树的根节点的值小于儿子节点的值。
左偏树的距离：左偏树中某个点的距离定义为从该点的右子树到达一个没有右儿子的点的距离，叶子节点的距离为0，**（y总是另一种定义方式：左偏树中某个点的距离定义为该点到最近的空节点的距离，此时叶子节点的距离是1，空节点的距离是0）**左偏指的是左子树的距离大于等于右子树的距离。
左偏树的操作：合并左偏树O(log n)、插入左偏树O(log n)、删除根O(log n)、删除任意节点

求最小值O(1)
堆中的左子树和右子树没有val上的关系，只要两者都比val[root]小就行

$重要性质：一个有n个节点的左偏树，根节点的距离dis[root]<=log \ n\\ 定义 f(k) 距离为k的子树，至少包含多少个节点,欲证f(k)>=2^k-1\\ 由数学归纳法，k=1时，f(1)=1，成立；假设k=n-1时f(k)=f(n-1)>=2^(n-1)-1;\\ 当k=n时，f(k)=f(n)>=2*f(k-1)+1==2^n-2+1==2^n-1,得证$

$已知距离为k的子树至少包含2^k-1个节点，那么包含n个节点的子树的最大距离是多少？\\ 2^k-1<=n,解得k<=log_2(n)+1,所以k是log级别的$

左偏树操作

$m e r g e (a, b) ；$ 合并两棵子树，返回合并后的根节点。
找到a，b中根节点值较小的那个，假设val[a]<val[b]，那么子树a的a作为新的树的根节点，
子树a的左子树作为新树的左子树，将a的右子树和b进行合并，递归进行，当合并之后发现
左子树的dis<右子树的dis，那么swap两个子树，当某个子树和一个空节点合并，直接返回该
点和值作为新的树的根节点。

$假设两个子树的dis[a],dis[b]，那么合并两颗子树多大操作次数为dis[a]+dis[b]\\ O(log n)$
```
int merge(int a,int b)// 以idx进行合并
{
    if(!a||!b)return a+b;//边界
    if(val[a]>val[b])swap(a,b);//但关键字比较
    right[a]=merge(right[a],b);//右子树递归合并
    if(dis[left[a]]<dis[right[a]])//合并之后检查dis合法
        swap(left[a],right[a]);
   	dis[a]=dis[right[a]]+1;//更新dis[root]
    return a;
}
```
以merge为核心，进行删除最小值，需要把val[root]删掉，合并两个子树即可。

AcWing 2714. 左偏树

在这里插入图片描述

并查集可以做没有分离，只有合并的操作的
因为需要快速找到每个元素所在左偏树的根节点，所以使用了并查集进行了维护。
因为操作2需要把两个具有idx属性的数进行合并，我们需要知道他们在不在同一个集合里，所以需要维护一堆左偏树的同时，对于每一个左偏树维护一个对应的并查集，并查集的代表元素就是左偏树的根节点。 
对于第4个操作，将左偏树中的某个点删掉，然后将合并之后的左偏树的新的根节点作为原来并查集的代表元素即可，使用了并查集的换根操作。

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

const int N=2e5+10;

int val[N],dis[N],l[N],r[N],idx;
int fa[N],n;

int find(int x)
{
    if(x!=fa[x])return fa[x]=find(fa[x]);
}

bool cmp(int x,int y)//idx之间的比较
{
    if(val[x]!=val[y])return val[x]<val[y];
    return x<y;
}

int merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(cmp(y,x))swap(x,y);
    r[x] = merge(r[x],y);
    if(dis[l[x]]<dis[r[x]])
        swap(l[x],r[x]);
    dis[x]=dis[r[x]]+1;
    return x;
}

int main()
{
    cin>>n;
    val[0]=2e9;//防止第4步0作为根节点
    while(n--)
    {
        int a,x,y;cin>>a>>x;
        if(a==1)
        {
            val[++idx]=x;
            fa[idx]=idx;
        }
        else if(a==2)
        {
            cin>>y;
            int pa=find(x),pb=find(y);
            if(pa!=pb)
            {
                if(cmp(pb,pa))swap(pa,pb);  
                fa[pb]=pa;
                merge(pa,pb);
            }
                
        }
        else if(a==3)
        {
            cout<<val[find(x)]<<endl; 
        }
        else
        {
            x=find(x);
            if(cmp(r[x],l[x]))swap(l[x],r[x]);//r[x]，l[x]可能为空，
            // 此时l[x]作为新的根节点
            fa[x]=l[x],fa[l[x]]=l[x];
            merge(l[x],r[x]);
            
        }
    }
    return 0;
}