左偏树(Leftist Heap)

左偏树(Leftist Heap),又称左偏堆或左式堆,是一种支持高效合并的二叉堆结构。它以堆的形式维护元素,同时为每个节点记录一个称为距离(或零路径长)的属性,并强制左子树的距离不小于右子树,由此让合并操作只需沿着最短的右侧路径进行。

概述

普通二叉堆用数组实现,合并两个堆需要几乎重建,代价较高。左偏树用链式的二叉树表示,把合并作为最基本的操作,插入和删除最小值都可以借助合并来实现,因而在需要频繁合并堆的场景中十分有用。

核心原理

每个节点维护一个距离值,定义为该节点到最近的空子节点的路径长度。左偏性质要求:任一节点的左孩子距离不小于右孩子距离,这保证了从根沿右链走到空节点的长度是 O(log n) 级。

• 合并:递归地把根值较大的堆并入较小者的右子树;回溯时若某节点右孩子距离大于左孩子,则交换左右孩子以维持左偏性质,并更新距离。
• 插入:视为把单节点堆与原堆合并。
• 删除最小值:删去根节点后,合并其左右两棵子树。

应用场景

左偏树适用于需要频繁合并优先队列的场景,例如某些图论算法中集合的动态合并、可并堆的教学演示,以及配合并查集实现按值合并的启发式结构。它实现相对简洁,是可并堆家族中的经典成员。

常见问题

问:左偏树为什么合并快?答:左偏性质保证从根到某个空节点的最右路径长度为 O(log n),合并只沿这条短路径递归进行,因此单次合并是对数级复杂度。

问:它和斐波那契堆比如何?答:斐波那契堆在摊还意义下减小键更快,但常数大、实现复杂;左偏树实现简单、合并稳定为 O(log n),在只需合并而不常做减小键的场合更实用。