资源描述：
《计算机科学外文翻译》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、BinomialheapIncomputerscience,abinomialheapisaheapsimilartoabinaryheapbutalsosupportsquickmergingoftwoheaps.Thisisachievedbyusingaspecialtreestructure.Itisimportantasanimplementationofthemergeableheapabstractdatatype(alsocalledmeldableheap),whichisapriorityqueuesupportingmergeoperation.Bino
2、mialtreeAbinomialheapisimplementedasacollectionofbinomialtrees(comparewithabinaryheap,whichhasashapeofasinglebinarytree).Abinomialtreeisdefinedrecursively:·Abinomialtreeoforder0isasinglenode·Abinomialtreeoforderkhasarootnodewhosechildrenarerootsofbinomialtreesofordersk−1,k−2,...,2,1,0(inthi
3、sorder).Binomialtreesoforder0to3:Eachtreehasarootnodewithsubtreesofalllowerorderedbinomialtrees,whichhavebeenhighlighted.Forexample,theorder3binomialtreeisconnectedtoanorder2,1,and0(highlightedasblue,greenandredrespectively)binomialtree.Abinomialtreeoforderkhas2knodes,heightk.Becauseofitsun
4、iquestructure,abinomialtreeoforderkcanbeconstructedfromtwotreesoforderk−1triviallybyattachingoneofthemastheleftmostchildofrootoftheotherone.Thisfeatureiscentraltothemergeoperationofabinomialheap,whichisitsmajoradvantageoverotherconventionalheaps.Thenamecomesfromtheshape:abinomialtreeoforder
5、hasnodesatdepth.StructureofabinomialheapAbinomialheapisimplementedasasetofbinomialtreesthatsatisfythebinomialheapproperties:·Eachbinomialtreeinaheapobeystheminimum-heapproperty:thekeyofanodeisgreaterthanorequaltothekeyofitsparent.·Therecanonlybeeitheroneorzerobinomialtreesforeachorder,inclu
6、dingzeroorder.Thefirstpropertyensuresthattherootofeachbinomialtreecontainsthesmallestkeyinthetree,whichappliestotheentireheap.Thesecondpropertyimpliesthatabinomialheapwithnnodesconsistsofatmostlogn+1binomialtrees.Infact,thenumberandordersofthesetreesareuniquelydeterminedbythenumberofnodesn:
7、eachbinomialtreecorrespondstoonedigitinthebinaryrepresentationofnumbern.Forexamplenumber13is1101inbinary,,andthusabinomialheapwith13nodeswillconsistofthreebinomialtreesoforders3,2,and0(seefigurebelow).Exampleofabinomialheapcontaining13nodeswithdistinctke
