检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。
左偏树(Leftist Tree 或 Leftist Heap,又称左偏堆、左倾堆)是一种可以快速合并的可并堆,在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中都有着广泛应用。
#定义
左偏树是一种可并堆的实现。左偏树是一棵二叉树,它的节点除了和二叉树的节点一样具有左右子树指针(left、right)外,还有两个属性:键值(value)和距离(dist,部分英文文献中称为 s-value)。键值用于比较节点的大小。距离的定义如下:
当且仅当节点 的左子树或右子树为空时,节点被称作外节点(实际上保存在二叉树中的节点都是内节点,外节点是逻辑上存在而无需保存)。节点 的距离是节点 到它的后代中的最近的外节点所经过的边数。特别的,如果节点 本身是外节点,则它的距离为 ;而空节点的距离规定为 。
#性质
- 节点的键值小于或等于它的左右子节点的键值。
- 节点的左侧子节点的 值大于等于右子节点的 值。
- 由 可知,左偏树每个节点的 值都等于其右子节点的 值加 。
- 树根的 值不超过 。
#合并操作
合并两个堆时,由于要满足堆性质,先取值较小的那个根作为合并后堆的根节点,然后将这个根的左儿子作为合并后堆的左儿子,递归地合并其右儿子与另一个堆,作为合并后的堆的右儿子。为了满足左偏性质,合并后若左儿子的 值小于右儿子的 值,就交换两个儿子。
class LeftistTree<T>
C++1 |
|
#删除节点
删除操作直接将左右儿子进行合并即可。注意此处维护了一个指向父亲节点的指针。
class LeftistTree<T>
C++1 |
|
#代码实现
下面一个封装好的左偏树模板,支持泛型和自定义比较器,内部使用了智能指针来简化内存管理。
1 |
|