左偏树（可并堆）¶

二叉堆¶

从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。

堆性质：父亲的权值不小于儿子的权值（大根堆）

插入数：先插入在堆尾，然后向上调整（每次与父节点比较交换）

删除堆顶：先与堆尾交换，删除堆尾，将堆顶向下调整

左偏树（可并堆）¶

实现目标

实现一个可以合并的小根堆（即支持合并两个小根堆为一个的小根堆，动态维护）

定义

左偏树是一种具有**左偏性质**的**堆有序**的二叉树。注意，左偏树不是二叉堆。

左偏树的每一个节点存储的信息包括左右子节点l[x],r[x]、权值v[x]和距离dis[x]。

左儿子或右儿子为空的节点，称为外节点。**节点的距离**的定义：该节点到与其最近的外节点经过的边数。

我们规定，外节点的距离为0，空节点的距离为-1。

（批注：二叉堆是完全二叉树，而左偏树不是）如下图，都是左偏树

性质

性质1：堆的性质，对于任意节点\(v[x] \leq v[lc[x]],v[rc[x]]\)（小根堆）。性质2：左偏性质，左儿子的距离\(\geq \(右儿子的距离，\)dis[lc] \geq dis[rc]\)。性质3：任意节点的距离=其右儿子的距离+1，\(dis[x]=dis[rc]+1\)。根据性质3，我们可以知道为什么空节点的dis为-1了。性质4：一棵有n个节点的二叉树，根的\(dis\leq log(n+1)-1\)。

根据性质3，我们可以知道为什么空节点的dis为-1了

对于性质4，我们举例说明：

根的dis=2，说明至少有3层满二叉树。因为如果没有3层满二叉树，就比如上图中去掉点8或者点4，5，那么点3（或者点2）的dis就会是0，根的dis就是1.总结来说，就是对于有i层的满二叉树，才能保证在1~i-1层之内没有空节点

因为根的距离为x的二叉树至少有x+1层是满二叉树，那么至少有\(2^{x+1} - 1\)个节点。即n≥\(2^{x+1} - 1\)，所以\(x≤\log(n+1)-1\)。

合并操作¶

合并操作是左偏树最重要的操作： 1.维护堆的性质，先取值较小的那个根作为合并后的堆的根节点，然后递归合并其右儿子与另一个堆，作为合并后的堆的右儿子。 2.维护左偏性质，合并后若左儿子的dis小于右儿子的dis，就交换两个儿子。

在递推过程中，我们维护堆的性质。在回溯过程中，我们维护左偏性质（通过交换左右儿子）

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);//让x的v小于y,若相同,则让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;//返回新的根节点

}

维护左偏性质：图示

v[x]==v[y]?x>y:v[x]>v[y]：图示

递归合并：图示

复杂度分析

每次递归都会让其中一个堆的根节点dis-1：图示

例题 #1¶

如题，一开始有 \(n\) 个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：

1 x y：将第 \(x\) 个数和第 \(y\) 个数所在的小根堆合并（若第 \(x\) 或第 \(y\) 个数已经被删除或第 \(x\) 和第 \(y\) 个数在用一个堆内，则无视此操作）。
2 x：输出第 \(x\) 个数所在的堆最小数，并将这个最小数删除（若有多个最小数，优先删除先输入的；若第 \(x\) 个数已经被删除，则输出 \(-1\) 并无视删除操作）。

提示

【数据规模】

对于 \(30\%\) 的数据：\(n\le 10\)，\(m\le 10\)。对于 \(70\%\) 的数据：\(n\le 10^3\)，\(m\le 10^3\)。对于 \(100\%\) 的数据：\(n\le 10^5\)，\(m\le 10^5\)，初始时小根堆中的所有数都在 int 范围内。

实现方法¶

由于数字的编号被保存在节点信息内，而非节点下标，所以为了找到所谓的“第x个数”，我们要么就枚举每一个点。这显然是不行的。

步骤如下

性质与区别

如下图，这是并查集的图像。可能在左偏树中，x是堆顶，其左右儿子分别为y和z，但是在并查集中，下一定也为根（我们这样维护），但y和z的位置就不一定了。

所以在合并后，我们不仅仅要将x的左右儿子y，z的fa指向新的根（新的根会在y，z之间产生），我们也要将x的fa指向新的根，因为在并查集中，会有其他点直接与x相连。即并查集**不是二叉树，x虽可抛，x的儿子不可抛**。在x在左偏树中被删除后，我们不在并查集中删除它，而是将其作为一个中继点，好让原来的x在并查集中的儿子们找到新的fa，进行路径压缩。

模板代码¶

/*////////ACACACACACACAC///////////
       . Coding by Ntsc .
       . ToFind Chargcy .
       . Prove Yourself .
/*////////ACACACACACACAC///////////

#include<bits/stdc++.h>
#define ll long long
#define db double
#define rtn return
#define i1n int i=1;i<=n;i++
#define in1 int i=n;i>=1;i--
using namespace std;

const int N=2e5+5;
const int M=1e5;
const int Mod=1e5;
const int INF=1e5;

int v[N],rc[N],fa[N],lc[N],n,m,op,x,y,dis[N];

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);//让x的v小于y,若相同,则让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 find(int x){//极简并查集
    return (x==fa[x])?x:fa[x]=find(fa[x]);
}

signed main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&v[i]);
        fa[i]=i;//并查集初始化
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&op,&x);
        if(op==1){
            scanf("%d",&y);
            if(v[x]==-1||v[y]==-1)continue;//判断是否被删除
            x=find(x);y=find(y);//找到xy分别的并查集

            if(x!=y)fa[x]=fa[y]=merge(x,y);//判断是否在同一个堆中
        }else{
            if(v[x]==-1){
                printf("-1\n");
                continue;
            }x=find(x);
            printf("%d\n",v[x]);//x既是原x所在并查集的根，也是原来x所在的堆的根节点.既然是小根堆,那么根节点恰好是最小值.找到他即可
            v[x]=-1;//标记删除
            fa[lc[x]]=fa[rc[x]]=fa[x]=merge(lc[x],rc[x]);//合并x的两个儿子,抛弃x,并且返回新的根
        }
    }
    return 0;
}