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

《算法合集之《左偏树的特点及其应用》.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、左偏树的特点及其应用广东省中山市第一中学黄源河左偏树的定义左偏树(LeftistTree)是一种可并堆(MergeableHeap)，它除了支持优先队列的三个基本操作（插入，删除，取最小节点），还支持一个很特殊的操作——合并操作。左偏树是一棵堆有序(HeapOrdered)二叉树。左偏树满足左偏性质(LeftistProperty)。2左偏树的定义——左偏性质定义一棵左偏树中的外节点(ExternalNode)为左子树或右子树为空的节点。定义节点i的距离(dist(i))为节点i到它的后代中，最近的外节点所经过的边数。任

2、意节点的左子节点的距离不小于右子节点的距离（左偏性质）。由左偏性质可知，一个节点的距离等于以该节点为根的子树最右路径的长度。3左偏树的性质定理：若一棵左偏树有N个节点，则该左偏树的距离不超过log(N+1)-1。最右路径:A－C－G最右路径节点数=3距离=28个节点的左偏树的最大距离：log(8+1)-1=2ABD00012EHF0G01C最右路径长度即为左偏树的距离4左偏树的操作左偏树支持下面这些操作：MakeNull——初始化一棵空的左偏树Merge——合并两棵左偏树Insert——插入一个新节点Min——取

3、得最小节点DeleteMin——删除最小节点Delete——删除任意已知节点Decrease——减小一个节点的键值5左偏树的操作——合并合并操作是递归进行的adist(L1)aL1R’交换左右子树并更新根节点距离合并后的右

4、子树距离可能大于左子树距离8左偏树的操作——合并合并操作的代码如下：FunctionMerge(A,B)IfA=NULLThenreturnBIfB=NULLThenreturnAIfkey(B)dist(left(A))Thenswap(left(A),right(A))Ifright(A)=NULLThendist(A)←0Elsedist(A)←dist(right(A))+1returnA

5、EndFunction9左偏树的操作——合并下面是一个合并的例子：61218243718700120013108261711000Merge(3,6)10左偏树的操作——合并下面是一个合并的例子：61218243718782617Merge(8,6)Merge(3,6)11左偏树的操作——合并下面是一个合并的例子：3718782617Merge(8,7)Merge(8,6)Merge(3,6)12左偏树的操作——合并下面是一个合并的例子：18Merge(8,18)Merge(8,7)Merge(8,6)Merge(3,6

6、)NULL8261713左偏树的操作——合并下面是一个合并的例子：Merge(8,7)Merge(8,6)Merge(3,6)188261737701?14左偏树的操作——合并下面是一个合并的例子：Merge(8,6)Merge(3,6)1122617371886121824715左偏树的操作——合并下面是一个合并的例子：Merge(3,6)02?2617737188612182431016左偏树的操作——合并下面是一个合并的例子：Merge(3,6)2617737188612182431020117左偏树的操作——合并

7、合并操作都是一直沿着两棵左偏树的最右路径进行的。一棵N个节点的左偏树，最右路径上最多有log(N+1)个节点。因此，合并操作的时间复杂度为：O(logN1+logN2)=O(logN)18左偏树的操作——插入插入一个新节点把待插入节点作为一棵单节点左偏树合并两棵左偏树时间复杂度：O(logN)Merge19左偏树的操作——删除删除最小节点删除根节点合并左右子树时间复杂度：O(logN)Merge20例题：数字序列给定一个整数序列a1,a2,…,an，求一个不下降序列b1≤b2≤…≤bn，使得数列{ai}和{bi}的各

8、项之差的绝对值之和

9、a1-b1

10、+

11、a2-b2

12、+…+

13、an-bn

14、最小。数据规模：1≤n≤106,0≤ai≤2*10921假设数列a1,a2,…,ak的最优解为b1,b2,…,bk合并{bi}中相同的项，得到m个区间和数列s1,s2,…,sm显然，si为数列a中，下标在第i个区间内的各项的中位数。bb1b2b3b4