资源描述：
《计算机科学外文翻译》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、BinomialheapIncomputerscience,abinomialheapisaheapsimilartoabinaryheapbutalsosupportsquickmergingoftwoheaps.Thisisachievedbyusingaspecialtreestructure.Itisimportantasanimplementationofthemergeableheapabstractdatatype(alsocalledmeldableheap),whichisapriorityqueuesupportingmergeoperation.BinomialtreeA
2、binomialheapisimplementedasacollectionofbinomialtrees(comparewithabinaryheap,whichhasashapeofasinglebinarytree).Abinomialtreeisdefinedrecursively:·Abinomialtreeoforder0isasinglenode·Abinomialtreeoforderkhasarootnodewhosechildrenarerootsofbinomialtreesofordersk−1,k−2,...,2,1,0(inthisorder).Binomialtr
3、eesoforder0to3:Eachtreehasarootnodewithsubtreesofalllowerorderedbinomialtrees,whichhavebeenhighlighted.Forexample,theorder3binomialtreeisconnectedtoanorder2,1,and0(highlightedasblue,greenandredrespectively)binomialtree.Abinomialtreeoforderkhas2knodes,heightk.Becauseofitsuniquestructure,abinomialtree
4、oforderkcanbeconstructedfromtwotreesoforderk−1triviallybyattachingoneofthemastheleftmostchildofrootoftheotherone.Thisfeatureiscentraltothemergeoperationofabinomialheap,whichisitsmajoradvantageoverotherconventionalheaps.Thenamecomesfromtheshape:abinomialtreeoforderhasnodesatdepth.Structureofabinomial
5、heapAbinomialheapisimplementedasasetofbinomialtreesthatsatisfythebinomialheapproperties:·Eachbinomialtreeinaheapobeystheminimum-heapproperty:thekeyofanodeisgreaterthanorequaltothekeyofitsparent.·Therecanonlybeeitheroneorzerobinomialtreesforeachorder,includingzeroorder.Thefirstpropertyensuresthatther
6、ootofeachbinomialtreecontainsthesmallestkeyinthetree,whichappliestotheentireheap.Thesecondpropertyimpliesthatabinomialheapwithnnodesconsistsofatmostlogn+1binomialtrees.Infact,thenumberandordersofthesetreesareuniquelydeterminedbythenumberofnodesn:eachbinomialtreecorrespondstoonedigitinthebinaryrepres
7、entationofnumbern.Forexamplenumber13is1101inbinary,,andthusabinomialheapwith13nodeswillconsistofthreebinomialtreesoforders3,2,and0(seefigurebelow).Exampleofabinomialheapcontaining13nodeswithdistinctke
