Mini wiki
左偏树
编辑
左偏树,也可称为左偏堆、左倾堆,是
计算机科学
中的一种
树
,是一种
优先队列
实现方式,属于可并
堆
,在
信息学
中十分常见,在统计问题、最值问题、模拟问题和
贪心法
等等类型的题目中,左偏树都有着广泛的应用。
斜堆
是比左偏树更为一般的数据结构。
1
相关
斜堆
是
左偏树
的一个变种。斜堆是一棵保持堆有序的二叉树,但是它不满足左偏性质,或者说斜堆根本就没有“距离”这个概念——它不需要记录任何一个节点的距离。从结构上来说,所有的
左偏树
都是斜堆,但反之不然。