算法分析与设计2005春.课件.第13讲 清华大学：算法分析与设计

《算法分析与设计2005春.课件.第13讲 清华大学：算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、OverviewonHeapsOperationBinaryheapBinomialFibonacciheapheapCreationΘ(1)Θ(1)Θ(1)第13讲：Binomial&FibonacciInsertΘ(lgn)Ο(lgn)Θ(1)HeapsMinimumΘ(1)Ο(lgn)Θ(1)Extract-minΘ(lgn)Θ(lgn)Ο(lgn)清华大学UnionΘ(n)Ο(lgn)Θ(1)宋斌恒Decrease-keyΘ(lgn)Θ(lgn)Θ(1)DeleteΘ(lgn)Θ(lgn)Ο(lgn)清华大学宋斌恒2OverviewComparisonofthe

2、heaps•Mergeableheapssupportthefollowing7•Ifnotsupporttheoperationunionthantheoperations.binaryheapisbetterthanbinomialheap1.Createheap•Fibonacciheapistotallybetterthan2.Insertbinomialheapwithsupportingthemerging3.Minimum4.Extract-minoperationintheamortizedsense5.Union6.Decrease-key7.Dele

3、te清华大学宋斌恒3清华大学宋斌恒4CommonissuesBinomialtrees•Itisinefficienttosupporttheoperationof•BinomialtreesBkaredefinedreclusivelyassearchforallkindsoftheheaps,soitneeds–B0consistsofasinglenodetovisittheelementsbyitshandleorthe–TheBkconsistsoftwoBk-1thatarelinkedpointertogether:therootofoneBk-1isth

4、eleftmostchildofanotheroneBk-1.清华大学宋斌恒5清华大学宋斌恒61Depth0123B0B1B2B3清华大学宋斌恒7清华大学宋斌恒8PropertiesProofoftheproperties•ForbinomialtreeBk:•Allbyinduction,becauseitisdefined1.Thereare2knodes.recursively.Hereweomittheproof.2.Theheightofthetreeisk•课堂练习3.Thereareexactly(ki)nodesatdepthifori=0,1,2,…,

5、k4.Theroothasdegreek,whichisgreaterthanthatofanyothernode;moreoverifthechildrenoftherootarenumberedfromlefttorightbyk-1,k-2,…,2,1,0,childiistherootofsubtreeBi.清华大学宋斌恒9清华大学宋斌恒10第三条性质的证明Binomialheaps•AbinomialheapsHisasetofbinomialtreesthatsatisfiesthefollowingbinomial-heapproperties:–Min-

6、heapproperty:eachtreeinHobeythemin-heapproperty,whichmeansthatthekeyofeachnodeisgreatthanorequaltoitsparentkey–ForanykthereexistsatmostoneBkinH.清华大学宋斌恒11清华大学宋斌恒122Head[H]parentKeyvaluedegreeRightsibling节点数据Left-child结构清华大学宋斌恒13清华大学宋斌恒14关于右兄弟的法则等Operationsonbinomialheap•如果一个节点是其父节点的最右边的孩•

7、1.Creatinganewemptybinomialheap:子，则该节点没有右兄弟，否则其右兄head[H]Ånull弟为其父节点的比自己靠右的下一个孩•2.H.minimum1.yÅnull子。2.xÅhead[h]•如果是根节点，其父节点为空。3.minÅinfinity4.Whilex!=null•孩子节点指向其最左孩子，否则为空1.Ifkey[x]