數(shù)據(jù)結(jié)構(gòu)與算法分析第二版英文版課件chapter8

Primaryvs.SecondaryStoragePrimarystorage:Mainmemory(RAM)SecondaryStorage:PeripheraldevicesDiskdrivesTapedrives1/4/20231優(yōu)秀課件，精彩無限！Primaryvs.SecondaryStoragePComparisonsRAMisusuallyvolatile.RAMisabout1/4milliontimesfasterthandisk.MediumEarly1996Mid1997Early2000RAM$45.007.001.50Disk1Floppy0.500.360.25Tape0.030.010.0011/4/20232優(yōu)秀課件，精彩無限！ComparisonsMediumEarly1996MiGoldenRuleofFileProcessingMinimizethenumberofdiskaccesses!1.Arrangeinformationsothatyougetwhatyouwantwithfewdiskaccesses.2.Arrangeinformationtominimizefuturediskaccesses.Anorganizationfordataondiskisoftencalledafilestructure(p261).Disk-basedspace/timetradeoff(p74):Compressinformationtosaveprocessingtimebyreducingdiskaccesses.1/4/20233優(yōu)秀課件，精彩無限！GoldenRuleofFileProcessingDiskDrives1/4/20234優(yōu)秀課件，精彩無限！DiskDrives12/19/20224優(yōu)秀課件，精彩無SectorsAsectoristhebasicunitofI/O.Interleavingfactor:Physicaldistancebetweenlogicallyadjacentsectorsonatrack.1/4/20235優(yōu)秀課件，精彩無限！Sectors12/19/20225優(yōu)秀課件，精彩無限！TermsLocalityofReference:Whenrecordisreadfromdisk,nextrequestislikelytocomefromnearthesameplaceinthefile.Cluster:Smallestunitoffileallocation,usuallyseveralsectors.Extent:Agroupofphysicallycontiguousclusters.Internalfragmentation:Wastedspacewithinsectorifrecordsizedoesnotmatchsectorsize;wastedspacewithinclusteriffilesizeisnotamultipleofclustersize.1/4/20236優(yōu)秀課件，精彩無限！TermsLocalityofReference:WhSeekTimeSeektime:TimeforI/Oheadtoreachdesiredtrack.LargelydeterminedbydistancebetweenI/Oheadanddesiredtrack.Track-to-tracktime:Minimumtimetomovefromonetracktoanadjacenttrack.AverageSeektime:Averagetimetoreachatrackforrandomaccess.1/4/20237優(yōu)秀課件，精彩無限！SeekTimeSeektime:TimeforIOtherFactorsRotationalDelayorLatency:TimefordatatorotateunderI/Ohead.Onehalfofarotationonaverage.At7200rpm,thisis8.3/2=4.2ms.Transfertime:TimefordatatomoveundertheI/Ohead.At7200rpm:Numberofsectorsread/Numberofsectorspertrack*8.3ms.1/4/20238優(yōu)秀課件，精彩無限！OtherFactorsRotationalDelayDiskSpecExample16.8GBdiskon10platters=1.68GB/platter13,085tracks/platter256sectors/track512bytes/sectorTrack-to-trackseektime:2.2msAverageseektime:9.5ms4KBclusters,32clusters/track.Interleavingfactorof3.5400RPM1/4/20239優(yōu)秀課件，精彩無限！DiskSpecExample16.8GBdiskDiskAccessCostExample(1)Reada1MBfiledividedinto2048recordsof512bytes(1sector)each.Assumeallrecordsareon8contiguoustracks.Firsttrack:9.5+11.1/2+3x11.1=48.4msRemaining7tracks:2.2+11.1/2+3x11.1=41.1ms.Total:48.4+7*41.1=335.7ms1/4/202310優(yōu)秀課件，精彩無限！DiskAccessCostExample(1)ReDiskAccessCostExample(2)Reada1MBfiledividedinto2048recordsof512bytes(1sector)each.Assumeallfileclustersarerandomlyspreadacrossthedisk.256clusters.Clusterreadtimeis(3x8)/256ofarotationforabout1ms.256(9.5+11.1/2+11.1x3x(8/256))isabout4119.2ms.1/4/202311優(yōu)秀課件，精彩無限！DiskAccessCostExample(2)ReHowMuchtoRead?Readtimeforonetrack:9.5+11.1/2+3x11.1=48.4ms.Readtimeforonesector:9.5+11.1/2+(1/256)11.1=15.1ms.Readtimeforonebyte:9.5+11.1/2=15.05ms.Nearlyalldiskdrivesread/writeonesectorateveryI/Oaccess.Alsoreferredtoasapage.P288:8.2ifclustersarespreadrandomlyacrossthedisk?1/4/202312優(yōu)秀課件，精彩無限！HowMuchtoRead?ReadtimeforBuffersTheinformationinasectorisstoredinabufferorcache.IfthenextI/Oaccessistothesamebuffer,thennoneedtogotodisk.Thereareusuallyoneormoreinputbuffersandoneormoreoutputbuffers.1/4/202313優(yōu)秀課件，精彩無限！BuffersTheinformationinaseBufferPoolsAseriesofbuffersusedbyanapplicationtocachediskdataiscalledabufferpool.VirtualmemoryusesabufferpooltoimitategreaterRAMmemorybyactuallystoringinformationondiskand“swapping”betweendiskandRAM.1/4/202314優(yōu)秀課件，精彩無限！BufferPoolsAseriesofbufferBufferPools1/4/202315優(yōu)秀課件，精彩無限！BufferPools12/19/202215優(yōu)秀課件，精OrganizingBufferPoolsWhichbuffershouldbereplacedwhennewdatamustberead?First-in,First-out:Usethefirstoneonthequeue.LeastFrequentlyUsed(LFU):Countbufferaccesses,reusetheleastused.LeastRecentlyused(LRU):Keepbuffersonalinkedlist.Whenbufferisaccessed,bringittofront.Reusetheoneatend.If391047353827comeinto3-bufferpool(emptyinitially)?1/4/202316優(yōu)秀課件，精彩無限！OrganizingBufferPoolsWhichbBufferpoolADT(1)classBufferPool{//(1)MessagePassingpublic:virtualvoidinsert(void*space,intsz,intpos)=0;virtualvoidgetbytes(void*space,intsz,intpos)=0;};classBufferPool{//(2)BufferPassingpublic:virtualvoid*getblock(intblock)=0;virtualvoiddirtyblock(intblock)=0;virtualintblocksize()=0;};1/4/202317優(yōu)秀課件，精彩無限！BufferpoolADT(1)classBufferDesignIssuesDisadvantageofmessagepassing:Messagesarecopiedandpassedbackandforth.

Disadvantagesofbufferpassing:Theuserisgivenaccesstosystemmemory(thebufferitself)Theusermustexplicitlytellthebufferpoolwhenbuffercontentshavebeenmodified,sothatmodifieddatacanberewrittentodiskwhenthebufferisflushed.Thepointermightbecomestalewhenthebufferpoolreplacesthecontentsofabuffer.1/4/202318優(yōu)秀課件，精彩無限！DesignIssuesDisadvantageofmProgrammer’sViewofFilesLogicalviewoffiles:Anarrayofbytes.Afilepointermarksthecurrentposition.Threefundamentaloperations:Readbytesfromcurrentposition(movefilepointer)Writebytestocurrentposition(movefilepointer)Setfilepointertospecifiedbyteposition.1/4/202319優(yōu)秀課件，精彩無限！Programmer’sViewofFilesLogiC++FileFunctions#include<fstream.h>voidfstream::open(char*name,openmodemode);Example:ios::in|ios::binaryvoidfstream::close();fstream::read(char*ptr,intnumbytes);fstream::write(char*ptr,intnumbtyes);fstream::seekg(intpos);fstream::seekg(intpos,ios::curr);fstream::seekp(intpos);fstream::seekp(intpos,ios::end);1/4/202320優(yōu)秀課件，精彩無限！C++FileFunctions#include<fsExternalSortingProblem:Sortingdatasetstoolargetofitintomainmemory.Assumedataarestoredondiskdrive.Tosort,portionsofthedatamustbebroughtintomainmemory,processed,andreturnedtodisk.Anexternalsortshouldminimizediskaccesses.1/4/202321優(yōu)秀課件，精彩無限！ExternalSortingProblem:SortiModelofExternalComputationSecondarymemoryisdividedintoequal-sizedblocks(512,1024,etc…)AbasicI/Ooperationtransfersthecontentsofonediskblockto/frommainmemory.Undercertaincircumstances,readingblocksofafileinsequentialorderismoreefficient.(When?)PrimarygoalistominimizeI/Ooperations.Assumeonlyonediskdriveisavailable.1/4/202322優(yōu)秀課件，精彩無限！ModelofExternalComputationSKeySortingOften,recordsarelarge,keysaresmall.Ex:PayrollentrieskeyedonIDnumberApproach1:Readinentirerecords,sortthem,thenwritethemoutagain.Approach2:Readonlythekeyvalues,storewitheachkeythelocationondiskofitsassociatedrecord.Afterkeysaresortedtherecordscanbereadandrewritteninsortedorder.1/4/202323優(yōu)秀課件，精彩無限！KeySortingOften,recordsareSimpleExternalMergesort(1)Quicksortrequiresrandomaccesstotheentiresetofrecords.Better:ModifiedMerge-sortalgorithm.ProcessnelementsinQ(logn)passes.Agroupofsortedrecordsiscalledarun順串.1/4/202324優(yōu)秀課件，精彩無限！SimpleExternalMergesort(1)QSimpleExternalMergesort(2)Splitthefileintotwofiles.Readinablockfromeachfile.Takefirstrecordfromeachblock,outputtheminsortedorder.Takenextrecordfromeachblock,outputthemtoasecondfileinsortedorder.Repeatuntilfinished,alternatingbetweenoutputfiles.Readnewinputblocksasneeded.Repeatsteps2-5,exceptthistimeinputfileshaverunsoftwosortedrecordsthataremergedtogether.Eachpassthroughthefilesprovideslargerruns.1/4/202325優(yōu)秀課件，精彩無限！SimpleExternalMergesort(2)SSimpleExternalMergesort(3)1/4/202326優(yōu)秀課件，精彩無限！SimpleExternalMergesort(3)1ProblemswithSimpleMergesortIseachpassthroughinputandoutputfilessequential?Whathappensifallworkisdoneonasinglediskdrive?HowcanwereducethenumberofMerge-sortpasses?Ingeneral,externalsortingconsistsoftwophases:BreakthefilesintoinitialrunsMergetherunstogetherintoasinglerun.1/4/202327優(yōu)秀課件，精彩無限！ProblemswithSimpleMergesortBreakingaFileintoRunsGeneralapproach:Readasmuchofthefileintomemoryaspossible.Performanin-memorysort.Outputthisgroupofrecordsasasinglerun.1/4/202328優(yōu)秀課件，精彩無限！BreakingaFileintoRunsGenerReplacementSelection(1)Breakavailablememoryintoanarrayfortheheap,aninputbuffer,andanoutputbuffer.Fillthearrayfromdisk.Makeamin-heap.Sendthesmallestvalue(root)totheoutputbuffer.1/4/202329優(yōu)秀課件，精彩無限！ReplacementSelection(1)BreakReplacementSelection(2)Ifthenextkeyinthefileisgreaterthanthelastvalueoutput,thenReplacetherootwiththiskeyelseReplacetherootwiththelastkeyinthearrayAddthenextrecordinthefiletoanewheap(actually,stickitattheendofthearray).1/4/202330優(yōu)秀課件，精彩無限！ReplacementSelection(2)IfthRSExample1/4/202331優(yōu)秀課件，精彩無限！RSExample12/19/202231優(yōu)秀課件，精彩無ProblemswithSimpleMergeSimplemerge-sort:Placerunsintotwofiles.Mergethefirsttworunstooutputfile,thennexttworuns,etc.Repeatprocessuntilonlyonerunremains.Howmanypassesforrinitialruns?Istherebenefitfromsequentialreading?Isworkingmemorywellused?Needawaytoreducethenumberofpasses.1/4/202332優(yōu)秀課件，精彩無限！ProblemswithSimpleMergeSimpMulti-wayMerge(1)Withreplacementselection,eachinitialrunisseveralblockslong.Assumeeachrunisplacedinseparatefile.Readthefirstblockfromeachfileintomemoryandperformanr-waymerge.Whenabufferbecomesempty,readablockfromtheappropriaterunfile.Eachrecordisreadonlyoncefromdiskduringthemergeprocess.1/4/202333優(yōu)秀課件，精彩無限！Multi-wayMerge(1)WithreplacMulti-wayMerge(2)Inpractice,useonlyonefileandseektoappropriateblock.1/4/202334優(yōu)秀課件，精彩無限！Multi-wayMerge(2)InpracticeLimitstoMulti-wayMerge(1)Assumeworkingmemoryisbblocksinsize.Howmanyrunscanbeprocessedatonetime?Therunsare2bblockslong(onaverage).Howbigafilecanbemergedinonepass?1/4/202335優(yōu)秀課件，精彩無限！LimitstoMulti-wayMerge(1)ALimitstoMulti-wayMerge(2)Largerfileswillneedmorepasses--buttherunsizegrowsquickly!Inkmergepasses,weprocess2b(k+1)blocks.Example:0.5MBworkingmemory,4KBblocks,yield128blocksforworkingmemory.Averagerunsizeis1MB,so128MBcanbesortedinonepassonaverage.16GBintwomergepasses.1/4/202336優(yōu)秀課件，精彩無限！LimitstoMulti-wayMerge(2)LGeneralPrinciplesAgoodexternalsortingalgorithmwillseektodothefollowing:Maketheinitialrunsaslongaspossible.Atallstages,overlap重疊、并行input,processingandoutputasmuchaspossible.Useasmuchworkingmemoryaspossible.Applyingmorememoryusuallyspeedsprocessing.Ifpossible,useadditionaldiskdrivesformoreoverlappingofprocessingwithI/O,andallowformoresequentialfileprocessing.1/4/202337優(yōu)秀課件，精彩無限！GeneralPrinciplesAgoodexterExerciseP2888.2,8.3,8.81/4/202338優(yōu)秀課件，精彩無限！ExerciseP28812/19/202238優(yōu)秀課件，精Primaryvs.SecondaryStoragePrimarystorage:Mainmemory(RAM)SecondaryStorage:PeripheraldevicesDiskdrivesTapedrives1/4/202339優(yōu)秀課件，精彩無限！Primaryvs.SecondaryStoragePComparisonsRAMisusuallyvolatile.RAMisabout1/4milliontimesfasterthandisk.MediumEarly1996Mid1997Early2000RAM$45.007.001.50Disk1Floppy0.500.360.25Tape0.030.010.0011/4/202340優(yōu)秀課件，精彩無限！ComparisonsMediumEarly1996MiGoldenRuleofFileProcessingMinimizethenumberofdiskaccesses!1.Arrangeinformationsothatyougetwhatyouwantwithfewdiskaccesses.2.Arrangeinformationtominimizefuturediskaccesses.Anorganizationfordataondiskisoftencalledafilestructure(p261).Disk-basedspace/timetradeoff(p74):Compressinformationtosaveprocessingtimebyreducingdiskaccesses.1/4/202341優(yōu)秀課件，精彩無限！GoldenRuleofFileProcessingDiskDrives1/4/202342優(yōu)秀課件，精彩無限！DiskDrives12/19/20224優(yōu)秀課件，精彩無SectorsAsectoristhebasicunitofI/O.Interleavingfactor:Physicaldistancebetweenlogicallyadjacentsectorsonatrack.1/4/202343優(yōu)秀課件，精彩無限！Sectors12/19/20225優(yōu)秀課件，精彩無限！TermsLocalityofReference:Whenrecordisreadfromdisk,nextrequestislikelytocomefromnearthesameplaceinthefile.Cluster:Smallestunitoffileallocation,usuallyseveralsectors.Extent:Agroupofphysicallycontiguousclusters.Internalfragmentation:Wastedspacewithinsectorifrecordsizedoesnotmatchsectorsize;wastedspacewithinclusteriffilesizeisnotamultipleofclustersize.1/4/202344優(yōu)秀課件，精彩無限！TermsLocalityofReference:WhSeekTimeSeektime:TimeforI/Oheadtoreachdesiredtrack.LargelydeterminedbydistancebetweenI/Oheadanddesiredtrack.Track-to-tracktime:Minimumtimetomovefromonetracktoanadjacenttrack.AverageSeektime:Averagetimetoreachatrackforrandomaccess.1/4/202345優(yōu)秀課件，精彩無限！SeekTimeSeektime:TimeforIOtherFactorsRotationalDelayorLatency:TimefordatatorotateunderI/Ohead.Onehalfofarotationonaverage.At7200rpm,thisis8.3/2=4.2ms.Transfertime:TimefordatatomoveundertheI/Ohead.At7200rpm:Numberofsectorsread/Numberofsectorspertrack*8.3ms.1/4/202346優(yōu)秀課件，精彩無限！OtherFactorsRotationalDelayDiskSpecExample16.8GBdiskon10platters=1.68GB/platter13,085tracks/platter256sectors/track512bytes/sectorTrack-to-trackseektime:2.2msAverageseektime:9.5ms4KBclusters,32clusters/track.Interleavingfactorof3.5400RPM1/4/202347優(yōu)秀課件，精彩無限！DiskSpecExample16.8GBdiskDiskAccessCostExample(1)Reada1MBfiledividedinto2048recordsof512bytes(1sector)each.Assumeallrecordsareon8contiguoustracks.Firsttrack:9.5+11.1/2+3x11.1=48.4msRemaining7tracks:2.2+11.1/2+3x11.1=41.1ms.Total:48.4+7*41.1=335.7ms1/4/202348優(yōu)秀課件，精彩無限！DiskAccessCostExample(1)ReDiskAccessCostExample(2)Reada1MBfiledividedinto2048recordsof512bytes(1sector)each.Assumeallfileclustersarerandomlyspreadacrossthedisk.256clusters.Clusterreadtimeis(3x8)/256ofarotationforabout1ms.256(9.5+11.1/2+11.1x3x(8/256))isabout4119.2ms.1/4/202349優(yōu)秀課件，精彩無限！DiskAccessCostExample(2)ReHowMuchtoRead?Readtimeforonetrack:9.5+11.1/2+3x11.1=48.4ms.Readtimeforonesector:9.5+11.1/2+(1/256)11.1=15.1ms.Readtimeforonebyte:9.5+11.1/2=15.05ms.Nearlyalldiskdrivesread/writeonesectorateveryI/Oaccess.Alsoreferredtoasapage.P288:8.2ifclustersarespreadrandomlyacrossthedisk?1/4/202350優(yōu)秀課件，精彩無限！HowMuchtoRead?ReadtimeforBuffersTheinformationinasectorisstoredinabufferorcache.IfthenextI/Oaccessistothesamebuffer,thennoneedtogotodisk.Thereareusuallyoneormoreinputbuffersandoneormoreoutputbuffers.1/4/202351優(yōu)秀課件，精彩無限！BuffersTheinformationinaseBufferPoolsAseriesofbuffersusedbyanapplicationtocachediskdataiscalledabufferpool.VirtualmemoryusesabufferpooltoimitategreaterRAMmemorybyactuallystoringinformationondiskand“swapping”betweendiskandRAM.1/4/202352優(yōu)秀課件，精彩無限！BufferPoolsAseriesofbufferBufferPools1/4/202353優(yōu)秀課件，精彩無限！BufferPools12/19/202215優(yōu)秀課件，精OrganizingBufferPoolsWhichbuffershouldbereplacedwhennewdatamustberead?First-in,First-out:Usethefirstoneonthequeue.LeastFrequentlyUsed(LFU):Countbufferaccesses,reusetheleastused.LeastRecentlyused(LRU):Keepbuffersonalinkedlist.Whenbufferisaccessed,bringittofront.Reusetheoneatend.If391047353827comeinto3-bufferpool(emptyinitially)?1/4/202354優(yōu)秀課件，精彩無限！OrganizingBufferPoolsWhichbBufferpoolADT(1)classBufferPool{//(1)MessagePassingpublic:virtualvoidinsert(void*space,intsz,intpos)=0;virtualvoidgetbytes(void*space,intsz,intpos)=0;};classBufferPool{//(2)BufferPassingpublic:virtualvoid*getblock(intblock)=0;virtualvoiddirtyblock(intblock)=0;virtualintblocksize()=0;};1/4/202355優(yōu)秀課件，精彩無限！BufferpoolADT(1)classBufferDesignIssuesDisadvantageofmessagepassing:Messagesarecopiedandpassedbackandforth.

Disadvantagesofbufferpassing:Theuserisgivenaccesstosystemmemory(thebufferitself)Theusermustexplicitlytellthebufferpoolwhenbuffercontentshavebeenmodified,sothatmodifieddatacanberewrittentodiskwhenthebufferisflushed.Thepointermightbecomestalewhenthebufferpoolreplacesthecontentsofabuffer.1/4/202356優(yōu)秀課件，精彩無限！DesignIssuesDisadvantageofmProgrammer’sViewofFilesLogicalviewoffiles:Anarrayofbytes.Afilepointermarksthecurrentposition.Threefundamentaloperations:Readbytesfromcurrentposition(movefilepointer)Writebytestocurrentposition(movefilepointer)Setfilepointertospecifiedbyteposition.1/4/202357優(yōu)秀課件，精彩無限！Programmer’sViewofFilesLogiC++FileFunctions#include<fstream.h>voidfstream::open(char*name,openmodemode);Example:ios::in|ios::binaryvoidfstream::close();fstream::read(char*ptr,intnumbytes);fstream::write(char*ptr,intnumbtyes);fstream::seekg(intpos);fstream::seekg(intpos,ios::curr);fstream::seekp(intpos);fstream::seekp(intpos,ios::end);1/4/202358優(yōu)秀課件，精彩無限！C++FileFunctions#include<fsExternalSortingProblem:Sortingdatasetstoolargetofitintomainmemory.Assumedataarestoredondiskdrive.Tosort,portionsofthedatamustbebroughtintomainmemory,processed,andreturnedtodisk.Anexternalsortshouldminimizediskaccesses.1/4/202359優(yōu)秀課件，精彩無限！ExternalSortingProblem:SortiModelofExternalComputationSecondarymemoryisdividedintoequal-sizedblocks(512,1024,etc…)AbasicI/Ooperationtransfersthecontentsofonediskblockto/frommainmemory.Undercertaincircumstances,readingblocksofafileinsequentialorderismoreefficient.(When?)PrimarygoalistominimizeI/Ooperations.Assumeonlyonediskdriveisavailable.1/4/202360優(yōu)秀課件，精彩無限！ModelofExternalComputationSKeySortingOften,recordsarelarge,keysaresmall.Ex:PayrollentrieskeyedonIDnumberApproach1:Readinentirerecords,sortthem,thenwritethemoutagain.Approach2:Readonlythekeyvalues,storewitheachkeythelocationondiskofitsassociatedrecord.Afterkeysaresortedtherecordscanbereadandrewritteninsortedorder.1/4/202361優(yōu)秀課件，精彩無限！KeySortingOften,recordsareSimpleExternalMergesort(1)Quicksortrequiresrandomaccesstotheentiresetofrecords.Better:ModifiedMerge-sortalgorithm.ProcessnelementsinQ(logn)passes.Agroupofsortedrecordsiscalledarun順串.1/4/202362優(yōu)秀課件，精彩無限！SimpleExternalMergesort(1)QSimpleExternalMergesort(2)Splitthefileintotwofiles.Readinablockfromeachfile.Takefirstrecordfromeachblock,outputtheminsortedorder.Takenextrecordfromeachblock,outputthemtoasecondfileinsortedorder.Repeatuntilfinished,alternatingbetweenoutputfiles.Readnewinputblocksasneeded.Repeatsteps2-5,exceptthistimeinputfileshaverunsoftwosortedrecordsthataremergedtogether.Eachpassthroughthefilesprovideslargerruns.1/4/202363優(yōu)秀課件，精彩無限！SimpleExternalMergesort(2)SSimpleExternalMergesort(3)1/4/202364優(yōu)秀課件，精彩無限！SimpleExternalMergesort(3)1ProblemswithSimpleMergesortIseachpassthroughinputandoutputfilessequential?Whathappensifallworkisdoneonasinglediskdrive?HowcanwereducethenumberofMerge-sortpasses?Ingeneral,externalsortingconsistsoftwophases:BreakthefilesintoinitialrunsMergetherunstogetherintoasinglerun.1/4/202365優(yōu)秀課件，精彩無限！ProblemswithSimpleMergesortBreakingaFileintoRunsGeneralapproach:Readasmuchofthefileintomemoryaspossible.Performanin-memorysort.Outputthisgroupofrecordsasasinglerun.1/4/202366優(yōu)秀課件，精彩無限！BreakingaFileintoRunsGenerReplacementSelection(1)Breakavailablememoryintoanarrayfortheheap,aninputbuffer,andanoutputbuffer.Fillthearrayfromdisk.Makeamin-heap.Sendthesmallestvalue(root)totheoutputbuffer.1/4/202367優(yōu)秀課件，精彩無限！ReplacementSelection(1)BreakReplacementSelection(2)Ifthenextkeyinthefileisgreaterthanthelastvalueoutput,thenReplacetherootwiththiskeyelseReplace