左偏树【学习笔记】

前置芝士：堆

可并堆

可并堆就是满足堆性质且可以在$O(\log{n})$的复杂度内合并两个堆的数据结构。常见的有斜堆，左偏树等。

这篇文章就来介绍一下左偏树。

首先有个问题：直接用二叉堆不香吗？

答案是肯定的。因为二叉堆合并的时间复杂度是$O(n)$的。

所以我们有了左偏树这个数据结构。

左偏树

一些记号与定义

val：每个节点的权值，堆按这个排序。

外节点：没有左孩子或右孩子或都没有的节点。

dist：空节点的dist是0，外节点的dist是1，其余节点的dist为到最近的外节点的距离。

一棵左偏树的dist：记堆顶的dist为这课左偏树的dist。

性质

左偏树顾名思义就是朝左偏的树。它在满足堆性质的基础上还要满足左孩子的dist大于等于右孩子的dist（所以左偏嘛）。

在合并时全部怼到右孩子去就可以保证在log的时间复杂度内合并了。

显然，对于一个非外节点的dist等于其右孩子的dist+1。

基本操作

合并

合并时左偏树最重要的一步，我们以小根堆为例。

假设我们要合并两个堆的堆顶分别是u，v。

于是我们为了满足小根堆的性质找出val较小的点做为新左偏树的顶点，这里不妨设其为u。

于是基于启发式合并的思想，我们把u的右孩子和v合并，递归去做就可以了。

因为一棵左偏树的dist最多是$ceil(\log{n})$，每次合并必有一棵左偏树的dist减1，所以这样合并的复杂度是$O(\log{n}+\log{m})$。

合并完有可能打破左偏树的性质，要更新。

int Merge(int u, int v) {
    if (!u || !v) return u | v;
    if (val[u] > val[v]) swap(u, v);
    rson[u] = merge(rson[u], v);
    if (dist[lson[u]] < dist[rson[u]]) swap(lson[u], rson[u]);
    dist[u] = dist[rson[u]] + 1;
    return u;
}

查找最小（最大值）

直接返回堆顶即可。

删除最小（最大值）

合并堆顶的两个孩子即可

删除任意给定节点

注意这里指的是给定节点，就是说告诉你了是几号节点。左偏树是不能快速删除某个权值的所有节点的。

这东西没什么鸟用，反正我至今没有遇到这样的题，就不讲了。其实是我太弱了。

思想和删除堆顶类似。

建树

像并查集一样，每个点就是一棵左偏树，然后再合并即可。

插入新节点同理直接合并即可。

给整个堆加上或乘上某个数

类似于线段树懒标记的思想，给堆顶打个标记，合并的时候再通过pushdown下放下去。

后面有一道例题。

例题

罗马游戏（模板题）

Monkey King（维护大根堆）

[APIO2012]派遣（树上问题）

「JLOI2015」城池攻占（树上问题+打标记）

左偏树【学习笔记】

原文：https://www.cnblogs.com/zcr-blog/p/12759955.html