资源描述：
《计算机科学外文翻译》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、BinomialheapIncomputerscience,abinomialheapisaheapsimilartoabinaryheapbutalsosupportsquickmergingoftwoheaps.Thisisachievedbyusingaspecialtreestructure.Itisimportantasanimplementationofthemergeableheapabstractdatatype(alsocalledmeldableheap),whichisapriorityqueuesup
2、portingmergeoperation.BinomialtreeAbinomialheapisimplementedasacollectionofbinomialtrees(comparewithabinaryheap,whichhasashapeofasinglebinarytree).Abinomialtreeisdefinedrecursively:·Abinomialtreeoforder0isasinglenode·Abinomialtreeoforderkhasarootnodewhosechildrenar
3、erootsofbinomialtreesofordersk−1,k−2,...,2,1,0(inthisorder).Binomialtreesoforder0to3:Eachtreehasarootnodewithsubtreesofalllowerorderedbinomialtrees,whichhavebeenhighlighted.Forexample,theorder3binomialtreeisconnectedtoanorder2,1,and0(highlightedasblue,greenandredre
4、spectively)binomialtree.Abinomialtreeoforderkhas2knodes,heightk.Becauseofitsuniquestructure,abinomialtreeoforderkcanbeconstructedfromtwotreesoforderk−1triviallybyattachingoneofthemastheleftmostchildofrootoftheotherone.Thisfeatureiscentraltothemergeoperationofabinom
5、ialheap,whichisitsmajoradvantageoverotherconventionalheaps.Thenamecomesfromtheshape:abinomialtreeoforderhasnodesatdepth.StructureofabinomialheapAbinomialheapisimplementedasasetofbinomialtreesthatsatisfythebinomialheapproperties:·Eachbinomialtreeinaheapobeystheminim
6、um-heapproperty:thekeyofanodeisgreaterthanorequaltothekeyofitsparent.·Therecanonlybeeitheroneorzerobinomialtreesforeachorder,includingzeroorder.Thefirstpropertyensuresthattherootofeachbinomialtreecontainsthesmallestkeyinthetree,whichappliestotheentireheap.Thesecond
7、propertyimpliesthatabinomialheapwithnnodesconsistsofatmostlogn+1binomialtrees.Infact,thenumberandordersofthesetreesareuniquelydeterminedbythenumberofnodesn:eachbinomialtreecorrespondstoonedigitinthebinaryrepresentationofnumbern.Forexamplenumber13is1101inbinary,,and
8、thusabinomialheapwith13nodeswillconsistofthreebinomialtreesoforders3,2,and0(seefigurebelow).Exampleofabinomialheapcontaining13nodeswithdistinctke
