左偏树

Prologue

左偏树是一种合并复杂度很优秀的堆。下图就是一棵典型的左偏树,蓝色的数字为该节点的路径长。

  • 左偏树是一棵二叉树
  • 左偏树的每个节点上记录其左右儿子、点权、路径长
  • 从节点 xx 到以 xx 为根的子树中儿子不足两个的节点的最近距离称为路径长
  • 左儿子的路径长不小于右儿子的路径长
  • 每个节点的路径长等于其右儿子的路径长加 1

根据上面的定义可以看出,左偏树是非常不平衡的二叉树,但左偏树的左子树并不一定要大于右子树,下图中的树也是一棵合法的左偏树。

Why leftist tree

最常见堆是基于压入和弹出二叉堆,一般直接使用 STL 中的 priority_queue,所有操作均摊 O(logN)O(\log N) ,但完全不资瓷合并操作。手写二叉堆一次合并的复杂度为 O(NlogN)O(N\log N),几乎不可用。基于合并操作的左偏树是一种最简单的可并堆的实现方式,可以在 O(logN)O(\log N) 的时间下完成合并操作。除此之外常见的可并堆还有斜堆、配对堆、二项式堆、斐波那契堆,这些堆都被封装在平板电视库中。

操作

存储

由于左偏树是很不平衡的二叉树,因此需要用链式结构进行存储,每个节点保存左右儿子和父节点的下标、点权、路径长即可。

1
2
3
4
5
6
7
struct uuz {
int l,r,f,w,d;
#define l(x) t[x].l
#define r(x) t[x].r
bool operator > (const uuz& a) {return w> a.w;}
bool operator ==(const uuz& a) {return w==a.w;}
}t[_];

合并

合并是左偏树的基本操作。先令 wxwyw_x\leq w_y,然后递归地合并 xx 的右子树和 yy,并用得到的子树的根节点更新 xx 的右儿子。最后如果左儿子的路径长小于右儿子的路径长,就交换左右儿子以维护左偏树的形态。

以下图为例:

  • 112222 小,合并 772222
  • 772222 小,合并 25252222
  • 发现 25>2225>22,交换
  • 发现 2222 并没有右儿子直接让 2525 成为 2222 的右儿子
  • 回溯让新的子树的树根成为递归时的节点的右儿子
  • 如果不满足左偏性质就交换左右儿子
1
2
3
4
5
6
7
8
int unite(int x,int y) {
if(!x||!y) return x+y;
if(t[x]>t[y]) x^=y^=x^=y;
t[r(x)=unite(r(x),y)].f=x;
if(t[l(x)].d<t[r(x)].d) l(x)^=r(x)^=l(x)^=r(x);
t[x].d=t[r(x)].d+1;
return x;
}

查询堆顶

由于记录了每个节点的父节点,所以只要不断迭代寻找即可。注意此处虽然和并查集寻找代表元类似,但不可使用路径压缩,否则会破坏左偏树的形态。

1
2
3
int get(int x) {
while(t[x].f) x=t[x].f; return x;
}

删除堆顶

左偏树的操作都基于合并。删除堆顶时,将堆顶的权值赋为 -1,并清空左右儿子的父节点 ,最后合并左右儿子即可。

1
2
3
void del(const int& x) {
t[x].w=-1; t[l(x)].f=t[r(x)].f=0; unite(l(x),r(x));
}

Download

参考资料

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

笔记 数据结构

评论

您需要成为穿墙的邪仙以加载 Disqus。