左偏树
维基百科，自由的百科全书
左偏树（英语：leftist tree 或 leftist heap）是计算机科学中的一种树，是一种优先队列实现方式，属于可并堆，在信息学中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中,左偏树都有着广泛的应用。斜堆是左偏树的一个变种。
目录 |
定义 [编辑]
左偏树是一种可并堆的实现。左偏树是一棵二叉树,它的节点除了和二叉树的节点一样具有左右子树指针( left, right ) 外,还有两个属性: 键值和距离(dist)。键值上面已经说过,是用于比较节点的大小。距离的定义如下： 当且仅当节点 i 的左子树或右子树为空时，节点被称作外节点。节点 i 的距离是节点 i 到它的后代中,最近的外节点所经过的边数。特别的,如果节点 i 本身是外节点,则它的距离为 0;而空节点的距离规定为-1 。[1]
性质 [编辑]
- 节点的键值小于或等于它的左右子节点的键值。
- 节点的左子节点的距离不小于右子节点的距离。
- 节点的距离等于它的右子节点的距离加1。
- 一棵N个节点的左偏树距离最多为log(N+1)-1。
参考文献 [编辑]
- ^ 《左偏树的特点及其应用》 黄源河 2005全国青少年信息学奥林匹克竞赛冬令营国家集训队论文
延伸阅读 [编辑]
- 傅清祥,王晓东 算法与数据结构(第二版) 电子工业出版社
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms (Second Edition) The MIT Press
- Mark Allen Weiss Data Structures and Algorithm Analysis in C (Second Edition) Pearson Education
