斜堆(Skew Heap)

斜堆是一种自调整的可合并二叉堆,可视作左偏树去掉距离标记后的简化版本。它不维护任何平衡信息,而是在每次合并时无条件交换左右子树,依靠摊还机制保证整体高效。

概述

斜堆的所有操作都归结为合并。它与左偏树同属可并堆家族,但左偏树需要记录并比较每个节点的零路径长度来决定是否交换子树,而斜堆索性每次都交换,省去了额外字段。这种大胆的策略让实现极为精简,同时通过势能分析仍能保证对数摊还复杂度。

核心特点

• 无需距离字段:相比左偏树节省存储,结构更轻量。
• 合并规则:递归合并两堆的右子树,合并完成后强制交换当前节点的左右孩子。
• 插入与删除:插入是与单节点合并,删除最小值是移除根后合并其左右子树。
• 摊还分析:借助以右重路径为势能的论证,证明单次操作摊还为对数级。

应用场景

斜堆适用于需要频繁合并优先队列的场景,如某些图算法与事件模拟。在教学中,它常作为自调整数据结构和摊还分析的经典范例。由于代码短小,竞赛选手也常用它来快速实现可并堆。

常见问题

问:斜堆与左偏树有何区别?答:左偏树按零路径长度有条件地交换子树,能保证单次操作最坏对数复杂度;斜堆无条件交换、不存距离,只有摊还对数保证,但实现更简单。

问:斜堆的单次操作会不会退化?答:单次合并在最坏情况下可能较慢,但连续操作的摊还成本仍是对数级,总体性能稳定。