资源描述：
《Mark Allen Weiss 数据结构与算法分析 课后习题答案6.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、Chapter6:PriorityQueues(Heaps)6.1Yes.Whenanelementisinserted,wecompareittothecurrentminimumandchangetheminimumifthenewelementissmaller.DeleteMinOoperationsareexpensiveinthisscheme.6.21132326754126481514129101113815149751113106.3TheresultofthreeDeleteMins,Ostartingwithbothoft
2、heheapsinExercise6.2,isasfol-lows:4465651371081271081514129111514913116.46.5Thesearesimplemodi®cationstothecodepresentedinthetextandmeantasprogrammingexercises.6.6225.Toseethis,startwithiO=1andpositionattheroot.Followthepathtowardthelastnode,doublingiOwhentakingaleftchild,an
3、ddoublingiOandaddingonewhentakingarightchild.-29-6.7(a)WeshowthatHO(NO),whichisthesumoftheheightsofnodesinacompletebinarytreeofNOnodes,isNO-bO(NO),wherebO(NO)isthenumberofonesinthebinaryrepresentationofNO.ObservethatforNO=0andNO=1,theclaimistrue.Assumethatitistrueforvaluesof
4、kOuptoandincludingNO-1.SupposetheleftandrightsubtreeshaveLOandROnodes,respectively.SincetheroothasheightOIlogNOK,wehaveHO(NO)=OIlogNOK+HO(LO)+HO(RO)=OIlogNOK+LO-bO(LO)+RO-bO(RO)=NO-1+(OIlogNOK-bO(LO)-bO(RO))Thesecondlinefollowsfromtheinductivehypothesis,andthethirdfollowsbec
5、auseLO+RO=NO-1.Nowthelastnodeinthetreeisineithertheleftsubtreeortherightsub-tree.Ifitisintheleftsubtree,thentherightsubtreeisaperfecttree,andbO(RO)=OIlogNOK-1.Further,thebinaryrepresentationofNOandLOareidentical,withtheexceptionthattheleading10inNObecomes1inLO.(Forinstance,i
6、fNO=37=100101,LO=10101.)ItisclearthattheseconddigitofNOmustbezeroifthelastnodeisintheleftsub-tree.Thusinthiscase,bO(LO)=bO(NO),andHO(NO)=NO-bO(NO)Ifthelastnodeisintherightsubtree,thenbO(LO)=OIlogNOK.ThebinaryrepresentationofROisidenticaltoNO,exceptthattheleading1isnotpresent
7、.(Forinstance,ifNO=27=101011,LO=01011.)ThusbO(RO)=bO(NO)-1,andagainHO(NO)=NO-bO(NO)(b)Runasingle-eliminationtournamentamongeightelements.Thisrequiressevencom-parisonsandgeneratesorderinginformationindicatedbythebinomialtreeshownhere.aecbgfdhTheeighthcomparisonisbetweenbOandc
8、O.IfcOislessthanbO,thenbOismadeachildofcO.Otherwise,bothcOanddOaremadechild
