算法合集之《左偏树的特点及其应用》.ppt

《算法合集之《左偏树的特点及其应用》.ppt》由会员分享，可在线阅读，更多相关《算法合集之《左偏树的特点及其应用》.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、左偏树的特点及其应用左偏树的特点及其应用广东省中山市第一中学广东省中山市第一中学广东省中山市第一中学广东省中山市第一中学 黄源河黄源河黄源河黄源河1Winter Camp 2005 演示稿左偏树的定义l左偏树左偏树(Leftist Tree)是一种可并堆可并堆(Mergeable Heap)，它除了支持优先队列的三个基本操作（插入，删除，取最小节点），还支持一个很特殊的操作合并操作。l左偏树是一棵堆有序堆有序(Heap Ordered)二叉树。l左偏树满足左偏性质左偏性质(Leftist Property)。2Winter Camp 2005 演示稿左偏树的定义 左偏性质l定义一棵左偏树中的外

2、节点外节点(External Node)为左子树或右子树为空的节点。l定义节点 i 的距离距离(dist(i)为节点 i 到它的后代中，最近的外节点所经过的边数。l任意节点的左子节点的距离不小于右子节点的距离（左偏性质）。l由左偏性质可知，一个节点的距离等于以该节点为根的子树最右路径的长度。3Winter Camp 2005 演示稿左偏树的性质l定理：若一棵左偏树有N个节点，则该左偏树的距离不超过 log(N+1)-1。最右路径:ACG最右路径节点数=3距离=28个节点的左偏树的最大距离：log(8+1)-1=2ABD00012EHF 0G 01C最右路径长度即为左偏树的距离4Winter C

3、amp 2005 演示稿左偏树的操作l左偏树支持下面这些操作：MakeNull 初始化一棵空的左偏树Merge 合并两棵左偏树Insert 插入一个新节点Min 取得最小节点DeleteMin 删除最小节点Delete 删除任意已知节点Decrease 减小一个节点的键值5Winter Camp 2005 演示稿左偏树的操作 合并l合并操作是递归进行的a dist(L1)aL1R交换左右子树并更新根节点距离合并后的右子树距离可能大于左子树距离8Winter Camp 2005 演示稿左偏树的操作 合并l合并操作的代码如下：Function Merge(A,B)If A=NULL Then re

4、turn 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 Function9Winter Camp 2005 演示稿左偏树的操作 合并l下面是一个合并的例子：61218243718700120013108261711000Merge(3,6)10Winter Camp 2005 演示稿左偏树的操作 合并l下面是一个合并的例子：61218243718782617Merg

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

6、示稿左偏树的操作 合并l下面是一个合并的例子：Merge(8,6)Merge(3,6)1122617371886121824715Winter Camp 2005 演示稿左偏树的操作 合并l下面是一个合并的例子：Merge(3,6)02?2617737188612182431016Winter Camp 2005 演示稿左偏树的操作 合并l下面是一个合并的例子：Merge(3,6)2617737188612182431020117Winter Camp 2005 演示稿左偏树的操作 合并l合并操作都是一直沿着两棵左偏树的最右路径进行的。l一棵N个节点的左偏树，最右路径上最多有 log(N+1)

7、个节点。l因此，合并操作的时间复杂度为：O(log N1+log N2)=O(log N)18Winter Camp 2005 演示稿左偏树的操作 插入l插入一个新节点把待插入节点作为一棵单节点左偏树合并两棵左偏树时间复杂度：O(log N)Merge19Winter Camp 2005 演示稿左偏树的操作 删除l删除最小节点删除根节点合并左右子树时间复杂度：O(log N)Merge20Winter Camp 2005 演示稿例题：数字序列l给定一个整数序列 a1,a2,an，求一个不下降序列 b1b2bn，使得数列 ai 和 bi 的各项之差的绝对值之和|a1-b1|+|a2-b2|+|a

8、n-bn|最小。l数据规模：1n106,0ai2*109 21Winter Camp 2005 演示稿l假设数列 a1,a2,ak 的最优解为 b1,b2,bkl合并 bi 中相同的项，得到 m 个区间和数列 s1,s2,sml显然，si 为数列 a 中，下标在第 i 个区间内的各项的中位数。bb1 b2 b3 b4 b5 b6 b7 b8 bk s1 s2 sm-1 smak+1加入ak+1后，怎样得到前k+1项的最优解？例题：数字序列 算法分析22Winter Camp 2005 演示稿l若ak+1sm，直接令sm+1ak+1，得到前k+1项的最优解；l否则，将ak+1并入第m个区间，并更

9、新sml不断 检查最后两个区间的解 sm-1和 sm，若sm-1sm，合并最后两个区间，并令新区间的解为该区间内的中位数。b s1 s2 sm-1 smak+1smsm-1例题：数字序列 算法分析23Winter Camp 2005 演示稿l下面考虑数据结构的选取l我们需要维护若干个有序集，并能够高效完成下面两个操作：合并两个有序集查询某个有序集的中位数l进一步分析，加入一个元素后，发生一连串合并操作，合并后有序集的中位数不会比原来大l因此，每个有序集内只保存较小的一半元素，查询中位数操作转化为取最大元素操作。例题：数字序列 算法分析24Winter Camp 2005 演示稿例题：数字序列

10、算法分析l现在，我们需要合并、取最大元素和删除三种操作，而这些都是可并堆的基本操作。l下表列出了几种可并堆相应操作的时间复杂度25Winter Camp 2005 演示稿例题：数字序列 算法分析l在本题中，合并操作和取最大元素操作少于 n次，删除操作不超过 n/2 次l由于合并次数比较多，二叉堆的合并操作太慢了，总时间复杂度也无法令人满意。l二项堆和Fibonacci堆某些操作比左偏树快，但对于本题，三者的总时间复杂度均为O(nlogn)l二项堆和Fibonacci堆的空间需求比较大，编程实现也远没有左偏树简单。l相比之下，本题用左偏树实现，时空复杂度都可以接受，编程实现也非常简单，是十分理想的选择。26Winter Camp 2005 演示稿总结l左偏树的特点：时空效率高编程复杂度低l左偏树的应用：可并堆优先队列性价比高性价比高补充二叉堆的不足补充二叉堆的不足27Winter Camp 2005 演示稿28