普通堆能够动态维护一个集合最值，以大根堆为例，支持$O(\log{n})$ 插入一个数、删除堆顶，$O(1)$ 获得堆顶（最值）。但不方便合并两个堆，尽管可以利用启发式合并，但启发式合并本质上还是暴力合并。为了更加高效合并堆，前人发明了很多可并堆，例如左偏树、配对堆、随机堆、斜堆、二项堆、斐波那契堆，左偏树常数小、代码容易编写，这里重点介绍左偏树。pb_ds 中提供了配对堆，感兴趣可以拓展学习。

为什么需要可并堆？

尽管平衡树能够动态维护集合最值，并且还支持高效删除、修改任意节点，但是平衡树无法高效合并两个集合，这就是可并堆不可被取代的原因。

支持将两个堆高效合并，就是可并堆。左偏树能够支持传统堆的所有操作，还可以删除或修改堆中任意节点（还支持可持久化），最关键的是能够支持高效合并。当然左偏树，常数小、代码容易编写，这对于竞赛选手来说非常友好。

什么是左偏树？

要定义左偏树，需要明确两个基本概念：外节点、到外节点距离 dis。

• 外节点：在二叉树上，儿子个数小于 $2$ 的节点。
• 到外节点距离：树上任意一个节点到最近外节点经过的边的条数。特殊地，外节点自身到外节点距离为 $0$ , 空节点到外节点距离为 $-1$。（部分资料空节点距离为 $0$ ，所有节点距离会增大 $1$）

左偏树，是一棵二叉树，首先满足堆的性质，并且满足左偏性质。左偏性质：每个节点左节点 dis 大于等于 右儿子 dis。构造的左偏性质是为了高效合并。

左偏树重要性质

为了方便描述，明确一下数组含义。

根据需要左偏树每个节点需要维护：左右儿子 ls[x],rs[x]、节点权值 val[x]、 距离 dis[x]。

由于经常需要尽快到达左偏树根，需要利用并查集快速找根。因此需要维护并查集代表 fa[x]。

如果需要删除任意节点(修改任意节点)，还需要维护每个节点在左偏树上的亲父亲节点，记为 up[x]。

• 性质1：满足堆的性质，以小根堆为例，每个节点权值都满足堆的性质，即 $val[x] \le min(val[ls[x]],val[rs[x]])$ 。左右儿子之间没有大小关系。

• 性质2：左偏性质，左儿子距离大于等于右儿子，即 $dis[ls[x]]\ge dis[rs[x]]$。

• 性质3：任意节点距离等于右儿子距离加 $1$ ,即 $dis[x]=dis[rs[x]]+1$ 。特殊规定 $dis[0]=-1$ ,这样之后不需要特殊判断，直接可以直接等于右儿子距离加 $1$.

• 性质4：$n$ 个节点的左偏树，树根的 $dis$ 最大，满足 $dis\le \log{(n+1)}-1$.

  • 证明：根的距离为 $x$ 的左偏树，那么二叉树上有 $x+1$ 层是满的，至少有 $2^{x+1}-1$ 个节点。即 $n\ge 2^{x+1}-1$ ,得到 $x \le \log{(n+1)}-1$.

• 性质5：每个节点 $dis$ ，代表节点子树内满的层数，数量级上小于 $O(\log{n})$。这条性质主要是为了说明删除一个节点，向上调整 dis 的复杂度。

核心操作：合并

左偏树核心操作就是合并，合并时要同时兼顾符合堆和左偏的性质。以合并小根堆为例（本文讨论都以小根堆为例），合并时选择权值小的节点作为整个合并后的根。然后递归合并其右儿子与另外一个堆，作为合并后根的右儿子。

合并之后，要维护左偏性质，如果右儿子dis 大于左儿子dis ，那么就交换两个儿子。

核心代码如下：

dis[0]=-1 ; //规定空节点 dis 为 -1 ，后面就不需要特判了
int merge(int x,int y)
{
    if(x==0||y==0)return x+y;
    //小根堆
    if(val[x]>val[y])swap(x,y);  //x 要做堆顶
    rs[x]=merge(rs[x],y);        //递归合并根的右儿子与另外一个堆

    //回溯 保证左偏性质
    if(dis[ls[x]]<dis[rs[x]])swap(ls[x],rs[x]);
    //更新根的距离
    dis[x]=dis[rs[x]]+1;
    //返回合并后的根
    return x;
}

递归合并过程，可以用下面两个左偏树实例如下：

合并时间复杂度分析

递归合并，每递归一层，其中一个堆的 dis 就减少 1，最终合并到两个堆空节点上，总的复杂度就是两个堆根 dis 之和，即 $O(\log{n}+\log{m})$ ,如下图：

---

模板题

1.P3377 【模板】可并堆 1

【题意简化】一开始有 $n(\le 10^5)$ 个小根堆，每个堆包含且仅包含一个数。$m(\le 10^5)$ 次操作:

• 1 x y : 将第 x 个数和第 y 个数所在的小根堆合并
• 2 x : 输出第 x 个数所在的堆最小数，并将这个最小数删除

【分析】比较常规的可并堆操作，只涉及到堆合并、求堆顶、删除堆顶。

使用左偏树实现时，需要特别注意，由于左偏树深度量级为 $O(n)$，不能直接一级一级往上爬暴力找堆的根，要结合并查集，快速跳转到堆的根节点。

删除堆顶，只需要合并堆的根节点 $x$ 的左右儿子，将左右儿子变为堆的新的根。需要特别注意，旧根 $x$ 不能直接删掉，要修改其 fa[x] 数组，让 fa[x] 等于新根。因为在并查集上，还有其他节点指向 $x$ ,这样操作 $x$ 就变成一个中转节点。

删除堆顶，核心参考代码：

 void pop(int x)  //删除 x 所在的堆顶
{
    if(del[x]){
        cout<<"-1\n";continue;  // 已经被删除了 
       }
    x=find(x);   //快速跳到堆根节点
    cout<<v[x]<<"\n";
    del[x]=true;
    //注意 x 的 fa[] 要修改为新根
    fa[ls[x]]=fa[rs[x]]=fa[x]=merge(ls[x],rs[x]);
}

完整参考代码：点击

其他类似模板题

• P2713 罗马游戏
  • 只涉及到合并堆、求堆顶、删除堆顶
• P1456 Monkey King
  • 虽然需要修改任意节点，但大根堆，节点权值只会改小。对于需要修改的节点，修改 $x$ 以上的树还是满足左偏树，$x$ 下面的合并就是一个新堆，然后再次合并就可以了。即修改 $x$，之后不会往上修改。

2.P11266 【模板】可并堆 2

【题意简化】你需要维护序列 $a_{1,\dots,n}$ 以及 $n(\le 10^6)$ 个集合 $S_{1,\dots,n}$，初始时 $S_i=\{i\}$。

接下来要进行以下四种操作共 $m(\le 10^6)$ 次，每次操作形如：

• 0 x y：表示将元素 $y$ 从集合 $S_x$ 中删去。保证此时元素 $y$ 在集合 $S_x$ 中。
• 1 x：表示询问 $\min_{i\in S_x} a_i$，保证此时集合 $S_x$ 非空。
• 2 x y：将集合 $S_y$ 中并入 $S_x$ 并清空集合 $S_y$。保证此时集合 $S_x,S_y$ 均非空，且此次操作后不会再出现涉及集合 $S_y$ 的操作。
• 3 x y z：表示将 $a_y$ 赋值为 $z$。保证此时元素 $y$ 在集合 $S_x$ 中，且 $z<a_y$。

【分析】题意有点绕，实际就是最开始给定 $n$ 个堆，每个堆一开始只有 $i$ ,对应权值为 $a_i$.

需要合并堆、查询堆中最小值、删除任意一个节点、修改任意一个节点。要维护小根堆，存在删除任意节点、修改任意节点。

思路一：左偏树

这里需要删除任意一个顶点，如果再利用并查集，发现无法真正删除节点 $x$，使用数组 rt[x] 表示集合 $x$ 的根节点。

删除后需要向上调整，利用 up[x] 一步一步往上调整，由于每次只删除一个节点 dis 最多减少 1 ，当遇到第一个节点 x 满足 dis[ls[x]] 严格大于 dis[rs[x]] 就会停止，即调整的都是左右 dis 相等的节点，那么量级就是 $O(\log{n})$，即删除节点向上调整时间复杂度为 $O(\log{n})$.

删除任意节点

void pushup(int x)
{
    int fa=up[x];
    while(fa)
    {
        if(dis[ls[fa]]<dis[rs[fa]])swap(ls[fa],rs[fa]);
        if(dis[fa]==dis[rs[fa]]+1)return;  //不需要向上调整

        dis[fa]=dis[rs[fa]]+1;
        fa=up[fa];    
    }
}
void Del(int x,int y)
//从集合 x 中删除 y 点
{
    int fa=up[y],root=merge(ls[y],rs[y]);

    if(fa==0) //y是堆顶
    {
        rt[x]=root;
        up[root]=0; //没有父亲
        return;
    }

    //直接接上 符合堆的性质
    if(ls[fa]==y)ls[fa]=root;
    else rs[fa]=root;
    up[root]=fa;

    //从root 向上修改 dis 
    pushup(root);  //向上修改复杂度为 O(log{n})
    return; 
}

修改任意节点

对于修改，可以先删除，再合并，核心参考代码

void modify(int x,int y,int z)
{
    //先删除
    Del(x,y);

    //清空
    val[y]=z; dis[y]=0; ls[y]=rs[y]=up[y]=0;
    //重新合并
    rt[x]=merge(rt[x],y);
}

参考代码：点击

思路二：使用 pb_ds

可持久化可并堆

3.P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院

---

其他题目

1.P1552 [APIO2012] 派遣

【题意简化】

【分析】

思路一：树上启发式合并

树上每个节点对应一个优先队列，树上启发式合并容器，容器内代表子树费用小的点集。合并后，如果容器内总和超过 $m$ , 循环去掉费用高的点，直到总和小于等于 $m$. 时间复杂度 $O(n\log^2{n})$.

参考代码：点击

思路二：可并堆

每个子树对应一个可并堆，可并堆内维护费用低的点，当总和超了 $m$ ,循环删除堆顶。dfs 的过程合并子树的堆，时间复杂度为 $O(n\log{n})$.

2.P4971 断罪者

3.P3261 [JLOI2015] 城池攻占

【题意简化】

【分析】题目要求所有战士都是从儿子进攻到父亲，那么可以将儿子节点对应的堆，合并到父亲节点，想到了可并堆。对于树上每个点，如果战士牺牲，那么就出堆，可以使用小根堆，优先淘汰战斗力弱的战士。

考虑到每个点向父亲方向转移要乘以 v[i](>0) 或者加上 v[i] ,堆的单调性不会破坏。 可以使用懒惰标记，表示堆整体的乘法标记( mul[i] )和加法标记( add[i] )。

合并之前下传标记，参考代码如下：

void pushdown(int x)  //下传标记
{
    if(mul[x]!=1 || add[x]!=0)
    {
        val[ls[x]]*=mul[x]; val[ls[x]]+=add[x];
        val[rs[x]]*=mul[x]; val[rs[x]]+=add[x];
        mul[ls[x]]*=mul[x]; add[ls[x]]*=mul[x]; add[ls[x]]+=add[x];
        mul[rs[x]]*=mul[x]; add[rs[x]]*=mul[x]; add[rs[x]]+=add[x];
        mul[x]=1; add[x]=0;
    }
}

完整参考代码：点击

4.P3273 [SCOI2011] 棘手的操作

5.P4331 [BalticOI 2004] Sequence

6.P10759 [BalticOI 2024] Jobs

---

参考文献

1.[IOI2005 国家集训队论文]左偏树的特点及其应用

学习完毕

{{ select(1) }}

• YES
• NO