左偏堆的特点及其应用

1、Winter Camp 2005 演示稿2左偏树的定义l左偏树左偏树(Leftist Tree)是一种可并堆可并堆(Mergeable Heap) ，它除了支持优先队列的三个基本操作（插入，删除，取最小节点），还支持一个很特殊的操作合并操作。l左偏树是一棵堆有序堆有序(Heap Ordered)二叉树。l左偏树满足左偏性质左偏性质(Leftist Property)。Winter Camp 2005 演示稿3左偏树的定义 左偏性质l定义一棵左偏树中的外节点外节点(External Node) 为左子树或右子树为空的节点。l定义节点 i 的距离距离(dist(i) 为节点 i 到它的后代中，最近

2、的外节点所经过的边数。l任意节点的左子节点的距离不小于右子节点的距离（左偏性质）。 l由左偏性质可知，一个节点的距离等于以该节点为根的子树最右路径的长度。Winter Camp 2005 演示稿4左偏树的性质l定理：若一棵左偏树有N个节点，则该左偏树的距离不超过 log(N+1) -1。最右路径: ACG最右路径节点数 = 3距离 = 28个节点的左偏树的最大距离：log(8+1) -1 = 2ABD00012EHF 0G 01C最右路径长度即为左偏树的距离Winter Camp 2005 演示稿5左偏树的操作l左偏树支持下面这些操作：MakeNull 初始化一棵空的左偏树Merge 合并两棵

3、左偏树Insert 插入一个新节点Min 取得最小节点DeleteMin 删除最小节点Delete 删除任意已知节点Decrease 减小一个节点的键值Winter Camp 2005 演示稿6左偏树的操作 合并l合并操作是递归进行的a dist(L1)aL1R交换左右子树并更新根节点距离合并后的右子树距离可能大于左子树距离Winter Camp 2005 演示稿9左偏树的操作 合并l合并操作的代码如下：Function Merge(A, B)If A = NULL Then return BIf B = NULL Then return AIf key(B) dist(left(A) The

4、nswap(left(A), right(A)If right(A) = NULL Then dist(A) 0Else dist(A) dist(right(A) + 1return AEnd FunctionWinter Camp 2005 演示稿10左偏树的操作 合并l下面是一个合并的例子：61218243718700120013108261711000Merge (3, 6)Winter Camp 2005 演示稿11左偏树的操作 合并l下面是一个合并的例子：61218243718782617Merge (8, 6)Merge (3, 6)Winter Camp 2005 演示稿12左

5、偏树的操作 合并l下面是一个合并的例子：3718782617Merge (8, 7)Merge (8, 6)Merge (3, 6)Winter Camp 2005 演示稿13左偏树的操作 合并l下面是一个合并的例子：18Merge (8,18)Merge (8, 7)Merge (8, 6)Merge (3, 6)NULL82617Winter Camp 2005 演示稿14左偏树的操作 合并l下面是一个合并的例子：Merge (8, 7)Merge (8, 6)Merge (3, 6)188261737701?Winter Camp 2005 演示稿15左偏树的操作 合并l下面是一个合并的

6、例子：Merge (8, 6)Merge (3, 6)11226173718861218247Winter Camp 2005 演示稿16左偏树的操作 合并l下面是一个合并的例子：Merge (3, 6)02?26177371886121824310Winter Camp 2005 演示稿17左偏树的操作 合并l下面是一个合并的例子：Merge (3, 6)26177371886121824310201Winter Camp 2005 演示稿18左偏树的操作 合并l合并操作都是一直沿着两棵左偏树的最右路径进行的。l一棵N个节点的左偏树，最右路径上最多有 log(N+1) 个节点。l因此，合并操作的时间复杂度为：O(log N1 + log N2) = O(log N)Winter Camp 2005 演示稿19左偏树的操作 插入l插入一个新节点把待插入节点作为一棵单节点左偏树合并两棵左偏树时间复杂度：O(log N)MergeWinter Camp 2005 演示稿20左偏树的操作 删除l删除最小节点删除根节点合并左右子树时间复杂度：O(log N)Merge