《左偏堆的特点及其应用PPT》由会员分享，可在线阅读，更多相关《左偏堆的特点及其应用PPT（22页珍藏版）》请在金锄头文库上搜索。
1、左偏树的特点及其应用广东省中山市第一中广东省中山市第一中学学 黄源河黄源河2左偏树的定义l左偏树左偏树(Leftist Tree)是一种可并堆可并堆(Mergeable Heap) ，它除了支持优先队列的三个基本操作（插入，删除，取最小节点），还支持一个很特殊的操作合并操作。l左偏树是一棵堆有序堆有序(Heap Ordered)二叉树。l左偏树满足左偏性质左偏性质(Leftist Property)。3左偏树的定义 左偏性质l定义一棵左偏树中的外节点外节点(External Node) 为左子树或右子树为空的节点。l定义节点 i 的距离距离(dist(i) 为节点 i 到它的后代中，最近的外节
2、点所经过的边数。l任意节点的左子节点的距离不小于右子节点的距离（左偏性质）。 l由左偏性质可知，一个节点的距离等于以该节点为根的子树最右路径的长度。4左偏树的性质l定理：若一棵左偏树有N个节点，则该左偏树的距离不超过 log(N+1) -1。最右路径最右路径: A: AC CG G最右路径节点数最右路径节点数 = 3 = 3距离距离 = 2 = 28 8个节点的左偏树的最大个节点的左偏树的最大距离：距离： log(8+1)log(8+1) -1 = 2 -1 = 2A AB BD D0 00 00 01 12 2E EH HF F 0 0G G0 01 1C C最右路径长度即最右路径长度即为左
3、偏树的距离为左偏树的距离5左偏树的操作l左偏树支持下面这些操作：MakeNull 初始化一棵空的左偏树Merge 合并两棵左偏树Insert 插入一个新节点Min 取得最小节点DeleteMin 删除最小节点Delete 删除任意已知节点Decrease 减小一个节点的键值6左偏树的操作 合并l合并操作是递归进行的a ba dist(L) dist(L1 1) )a aL L1 1R R交换左右子树交换左右子树并更新根节点并更新根节点距离距离合并后的右子合并后的右子树距离可能大树距离可能大于左子树距离于左子树距离9左偏树的操作 合并l合并操作的代码如下：Function Merge(A, B)
4、If A = NULL Then return BIf B = NULL Then return AIf key(B) dist(left(A) Thenswap(left(A), right(A)If right(A) = NULL Then dist(A) 0Else dist(A) dist(right(A) + 1return AEnd Function10左偏树的操作 合并l下面是一个合并的例子：6 6121218182424373718187 70 00 01 12 20 00 01 13 310108 8262617171 11 10 00 00 0Merge (3, Merge
5、 (3, 6)6)11左偏树的操作 合并l下面是一个合并的例子：6 6121218182424373718187 78 826261717Merge (8, Merge (8, 6)6)Merge (3, Merge (3, 6)6)12左偏树的操作 合并l下面是一个合并的例子：373718187 78 826261717Merge (8, Merge (8, 7)7)Merge (8, Merge (8, 6)6)Merge (3, Merge (3, 6)6)13左偏树的操作 合并l下面是一个合并的例子：1818Merge Merge (8,18)(8,18)Merge (8, Merge
6、 (8, 7)7)Merge (8, Merge (8, 6)6)Merge (3, Merge (3, 6)6)NULLNULL8 82626171714左偏树的操作 合并l下面是一个合并的例子：Merge (8, Merge (8, 7)7)Merge (8, Merge (8, 6)6)Merge (3, Merge (3, 6)6)18188 82626171737377 70 01 1? ?15左偏树的操作 合并l下面是一个合并的例子：Merge (8, Merge (8, 6)6)Merge (3, Merge (3, 6)6)1 11 12 226261717373718188
7、86 61212181824247 716左偏树的操作 合并l下面是一个合并的例子：Merge (3, Merge (3, 6)6)0 02 2? ?262617177 7373718188 86 61212181824243 3101017左偏树的操作 合并l下面是一个合并的例子：Merge (3, Merge (3, 6)6)262617177 7373718188 86 61212181824243 310102 20 01 118左偏树的操作 合并l合并操作都是一直沿着两棵左偏树的最右路径进行的。l一棵N个节点的左偏树，最右路径上最多有 log(N+1) 个节点。l因此，合并操作的时间复杂度为：O(log N1 + log N2) = O(log N)19左偏树的操作 插入l插入一个新节点把待插入节点作为一棵单节点左偏树合并两棵左偏树时间复杂度：O(log N)MergeMerge20左偏树的操作 删除l删除最小节点删除根节点合并左右子树时间复杂度：O(log N)MergeMerge21总结l左偏树的特点：时空效率高编程复杂度低l左偏树的应用：可并堆优先队列性价比高性价比高补充二叉堆的不足补充二叉堆的不足22
