资源描述：
《计算机科学外文翻译》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、BinomialheapIncomputerscience,abinomialheapisaheapsimilartoabinaryheapbutalsosupportsquickmergingoftwoheaps.Thisisachievedbyusingaspecialtreestructure.Itisimportantasanimplementationofthemergeableheapabstractdatatype(alsocalledmeldableheap),whichisapriorityqueuesupportin
2、gmergeoperation.BinomialtreeAbinomialheapisimplementedasacollectionofbinomialtrees(comparewithabinaryheap,whichhasashapeofasinglebinarytree).Abinomialtreeisdefinedrecursively:·Abinomialtreeoforder0isasinglenode·Abinomialtreeoforderkhasarootnodewhosechildrenarerootsofbino
3、mialtreesofordersk−1,k−2,...,2,1,0(inthisorder).Binomialtreesoforder0to3:Eachtreehasarootnodewithsubtreesofalllowerorderedbinomialtrees,whichhavebeenhighlighted.Forexample,theorder3binomialtreeisconnectedtoanorder2,1,and0(highlightedasblue,greenandredrespectively)binomia
4、ltree.Abinomialtreeoforderkhas2knodes,heightk.Becauseofitsuniquestructure,abinomialtreeoforderkcanbeconstructedfromtwotreesoforderk−1triviallybyattachingoneofthemastheleftmostchildofrootoftheotherone.Thisfeatureiscentraltothemergeoperationofabinomialheap,whichisitsmajora
5、dvantageoverotherconventionalheaps.Thenamecomesfromtheshape:abinomialtreeoforderhasnodesatdepth.StructureofabinomialheapAbinomialheapisimplementedasasetofbinomialtreesthatsatisfythebinomialheapproperties:·Eachbinomialtreeinaheapobeystheminimum-heapproperty:thekeyofanodei
6、sgreaterthanorequaltothekeyofitsparent.·Therecanonlybeeitheroneorzerobinomialtreesforeachorder,includingzeroorder.Thefirstpropertyensuresthattherootofeachbinomialtreecontainsthesmallestkeyinthetree,whichappliestotheentireheap.Thesecondpropertyimpliesthatabinomialheapwith
7、nnodesconsistsofatmostlogn+1binomialtrees.Infact,thenumberandordersofthesetreesareuniquelydeterminedbythenumberofnodesn:eachbinomialtreecorrespondstoonedigitinthebinaryrepresentationofnumbern.Forexamplenumber13is1101inbinary,,andthusabinomialheapwith13nodeswillconsistoft
8、hreebinomialtreesoforders3,2,and0(seefigurebelow).Exampleofabinomialheapcontaining13nodeswithdistinctke
