左偏树

前言

左偏树是一种可并堆，顾名思义，它支持快速合并。

定义

定义外界点为孩子数量小于等于 \(2\) 个的节点，\(dis(u)\) 表示节点 \(u\) 到最近的外节点经过的边数减 \(1\)。特别的，空节点的 \(dis\) 为 \(-1\)。

定义节点 \(u\) 权值为 \(val(u)\)，左、右儿子分别为 \(ls(u),rs(u)\)。左偏树中可以出现重复的元素。

定义一棵以 \(u\) 为根节点的左偏树，它满足

• \(dis(ls(u))\ge dis(rs(u))\)；
• 若有左右儿子，则左右子树均为左偏树。
• 以 \(u\) 为根节点的树是一个堆，即 \(val(u)\le val(ls(u)),val(rs(u))\)。

本文的左偏树均为小根堆。

性质

可得 \(dis(u)=dis(rs)+1\)。

操作

合并

合并是左偏树的基本操作。

设合并两棵左偏树 \(x,y\)，合并后根节点为 \(z\)，且 \(val(x)\le val(y)\)，则取 \(z\gets x\)，合并后的根节点左儿子为 \(ls\)