资源描述:
《《基本数据结构》ppt课件2》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、PriorityQueuesSell100IBM$122Sell300IBM$120Buy500IBM$119Buy400IBM$1187/22/20211PriorityQueuesPriorityQueueADTApriorityqueuestoresacollectionofitemsAnitemisapair(key,element)MainmethodsofthePriorityQueueADTinsertItem(k,o)insertsanitemwithkeykandelementoremoveMin(
2、)removestheitemwithsmallestkeyandreturnsitselementAdditionalmethodsminKey()returns,butdoesnotremove,thesmallestkeyofanitemminElement()returns,butdoesnotremove,theelementofanitemwithsmallestkeysize(),isEmpty()Applications:StandbyflyersAuctionsStockmarket7/22/20
3、212PriorityQueuesTotalOrderRelationKeysinapriorityqueuecanbearbitraryobjectsonwhichanorderisdefinedTwodistinctitemsinapriorityqueuecanhavethesamekeyMathematicalconceptoftotalorderrelationReflexiveproperty:xxAntisymmetricproperty:xyyxx=yTransitiveproperty:x
4、yyzxz7/22/20213PriorityQueuesComparatorADTAcomparatorencapsulatestheactionofcomparingtwoobjectsaccordingtoagiventotalorderrelationAgenericpriorityqueueusesanauxiliarycomparatorThecomparatorisexternaltothekeysbeingcomparedWhenthepriorityqueueneedstocomparetwok
5、eys,itusesitscomparatorMethodsoftheComparatorADT,allwithBooleanreturntypeisLessThan(x,y)isLessThanOrEqualTo(x,y)isEqualTo(x,y)isGreaterThan(x,y)isGreaterThanOrEqualTo(x,y)isComparable(x)7/22/20214PriorityQueuesSortingwithaPriorityQueueWecanuseapriorityqueuetosort
6、asetofcomparableelementsInserttheelementsonebyonewithaseriesofinsertItem(e,e)operationsRemovetheelementsinsortedorderwithaseriesofremoveMin()operationsTherunningtimeofthissortingmethoddependsonthepriorityqueueimplementationAlgorithmPQ-Sort(S,C)InputsequenceS,comp
7、aratorCfortheelementsofSOutputsequenceSsortedinincreasingorderaccordingtoCPpriorityqueuewithcomparatorCwhileS.isEmpty()eS.remove(S.first())P.insertItem(e,e)whileP.isEmpty()eP.removeMin()S.insertLast(e)7/22/20215PriorityQueuesSequence-basedPriorityQueueImplem
8、entationwithanunsortedsequenceStoretheitemsofthepriorityqueueinalist-basedsequence,inarbitraryorderPerformance:insertItemtakesO(1)timesincewecaninserttheitemat