282
Chapter6 PriorityQueues(Heaps)
1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
#include <functional>
5
#include <string>
6
using namespace std;
7
8
//Empty the priority queue and print itscontents.
9
template <typenamePriorityQueue>
10
void dumpContents(const string & msg, PriorityQueue & pq)
11
{
12
cout <<msg <<":" <<endl;
13
while( !pq.empty( ) )
14
{
15
cout << pq.top( )<< endl;
16
pq.pop( );
17
}
18
}
19
20
//Do some insertsand removes (done in dumpContents).
21
int main( )
22
{
23
priority_queue<int>
maxPQ;
24
priority_queue<int,vector<int>,greater<int>> minPQ;
25
26
minPQ.push( 4 ); minPQ.push( 3); minPQ.push( 5 );
27
maxPQ.push( 4 ); maxPQ.push( 3); maxPQ.push( 5 );
28
29
dumpContents( "minPQ", minPQ );
// 3 4 5
30
dumpContents( "maxPQ", maxPQ );
// 5 4 3
31
32
return 0;
33
}
Figure6.57 RoutinethatdemonstratestheSTLpriority_queue;thecommentshowsthe
expectedorderofoutput
6.9 PriorityQueuesintheStandardLibrary
ThebinaryheapisimplementedintheSTLbytheclasstemplatenamed
priority_queue
foundinthestandardheaderfile
queue
.TheSTLimplementsamax-heapratherthanamin-
heapsothelargestratherthansmallestitemistheonethatisaccessed.Thekeymember
functionsare:
How to add pdf to powerpoint presentation - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
convert pdf to powerpoint using; convert pdf file to powerpoint online
How to add pdf to powerpoint presentation - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
pdf to ppt converter online for large; changing pdf to powerpoint
Exercises
283
void push( const Object & & x x );
const Object & & top( ( ) const;
void pop( ( );
bool empty( );
void clear( );
push
adds
x
tothepriorityqueue,
top
returnsthelargestelementinthepriorityqueue,
and
pop
removesthelargestelementfromthepriorityqueue.Duplicatesareallowed;if
thereareseverallargestelements,onlyoneofthemisremoved.
The priority queue template is instantiated with h an n item m type,the containertype
(almostalwaysyouwouldwanttousea
vector
thatstorestheitems),andthecomparator;
defaultsareallowedforthelasttwoparameters,andthedefaultsyieldamax-heap.Using
a
greater
functionobjectasthecomparatoryieldsamin-heap.
Figure6.57showsatestprogramthatillustrateshowthe
priority_queue
classtemplate
canbeusedasboththedefaultmax-heapandamin-heap.
Summary
Inthischapter,wehaveseenvariousimplementationsandusesofthepriorityqueueADT.
Thestandardbinaryheapimplementationiselegantbecauseofitssimplicityandspeed.
Itrequiresnolinksandonlyaconstantamountofextraspace,yetsupportsthepriority
queueoperationsefficiently.
Weconsideredtheadditional
merge
operationanddevelopedthreeimplementations,
eachofwhichisuniqueinitsownway.Theleftistheapisawonderfulexampleofthe
powerofrecursion.Theskewheaprepresentsaremarkabledatastructurebecauseofthe
lackofbalancecriteria.Itsanalysis,whichwewillperforminChapter11,isinterestingin
itsownright.Thebinomialqueueshowshowasimpleideacanbeusedtoachieveagood
timebound.
Wehavealsoseenseveralusesofpriorityqueues,rangingfromoperatingsystems
schedulingtosimulation.WewillseetheiruseagaininChapters7,9,and10.
Exercises
6.1
Canboth
insert
and
findMin
beimplementedinconstanttime?
6.2
a. Showtheresultofinserting10,12,1,14,6,5,8,15,3,9,7,4,11,13,and2,
oneatatime,intoaninitiallyemptybinaryheap.
b.Showtheresultofusingthelinear-timealgorithmtobuildabinaryheapusing
thesameinput.
6.3
Show the result t of performing three
deleteMin
operations in the e heap of f the
previousexercise.
6.4
AcompletebinarytreeofNelementsusesarraypositions1toN.Supposewetry
touseanarrayrepresentationofabinarytreethatisnotcomplete.Determinehow
largethearraymustbeforthefollowing:
VB.NET PowerPoint: Use PowerPoint SDK to Create, Load and Save PPT
an empty PowerPoint file with our reliable .NET PPT document add-on; a fully customized blank PowerPoint file by using the smart PowerPoint presentation control
convert pdf to powerpoint with; pdf conversion to powerpoint
VB.NET PowerPoint: Sort and Reorder PowerPoint Slides by Using VB.
index = 1 End If correctOrder.Add(index) Next clip art or screenshot to PowerPoint document slide powerful & profession imaging controls, PDF document, image
pdf into powerpoint; converting pdf to ppt
284
Chapter6 PriorityQueues(Heaps)
a. abinarytreethathastwoextralevels(thatis,itisveryslightlyunbalanced)
b.abinarytreethathasadeepestnodeatdepth2logN
c. abinarytreethathasadeepestnodeatdepth4.1logN
d.theworst-casebinarytree
6.5
Rewritethe
BinaryHeap insert
routinebyplacingacopyoftheinserteditemin
position0.
6.6
HowmanynodesareinthelargeheapinFigure6.13?
6.7
a. Provethatforbinaryheaps,
buildHeap
doesatmost2N−2comparisonsbetween
elements.
b.Showthataheapofeightelementscanbeconstructedin eightcomparisons
betweenheapelements.

c. Giveanalgorithmtobuildabinaryheapin
13
8
N+O(logN)elementcompar-
isons.
6.8
Showthefollowingregardingthemaximumitemintheheap:
a. Itmustbeatoneoftheleaves.
b.ThereareexactlyN/2leaves.
c. Everyleafmustbeexaminedtofindit.

6.9
Showthattheexpecteddepthofthekthsmallestelementinalargecompleteheap
(youmayassumeN=2
k
−1)isboundedbylogk.
6.10
a. Giveanalgorithmtofindallnodeslessthansomevalue,X,inabinaryheap.
YouralgorithmshouldruninO(K),whereKisthenumberofnodesoutput.
b.Doesyouralgorithmextendtoanyoftheotherheapstructuresdiscussedinthis
chapter?
c. GiveanalgorithmthatfindsanarbitraryitemXinabinaryheapusingatmost
roughly3N/4comparisons.

6.11 Propose an algorithm toinsert Mnodesintoa binary heap on elementsin
O(M+logNloglogN)time.Proveyourtimebound.
6.12 WriteaprogramtotakeNelementsanddothefollowing:
a. Insertthemintoaheaponebyone.
b.Buildaheapinlineartime.
Comparethe running timeofbothalgorithms forsorted,reverse-ordered,and
randominputs.
6.13 Each
deleteMin
operationuses2logNcomparisonsintheworstcase.
a. Proposeaschemesothatthe
deleteMin
operationusesonlylogN+loglogN+
O(1)comparisonsbetweenelements.Thisneednotimplylessdatamovement.

b.Extend your r scheme in part (a) so that t only y logN+ logloglog+O(1)
comparisonsareperformed.

c. Howfarcanyoutakethisidea?
d.Dothesavingsincomparisonscompensatefortheincreasedcomplexityofyour
algorithm?
6.14 Ifad-heapisstoredasanarray,foranentrylocatedinpositioni,wherearethe
parentsandchildren?
VB.NET PowerPoint: VB Codes to Create Linear and 2D Barcodes on
Here is a market-leading PowerPoint barcode add-on within VB.NET class, which means it as well as 2d barcodes QR Code, Data Matrix, PDF-417, etc.
convert pdf document to powerpoint; how to add pdf to powerpoint presentation
VB.NET PowerPoint: Merge and Split PowerPoint Document(s) with PPT
For Each doc As [String] In dirs docList.Add(doc) Next code in VB.NET to finish PowerPoint document splitting If you want to see more PDF processing functions
how to convert pdf slides to powerpoint presentation; change pdf to powerpoint online
Exercises
285
6.15 SupposeweneedtoperformM
percolateUp
sandN
deleteMin
sonad-heapthat
initiallyhasNelements.
a. WhatisthetotalrunningtimeofalloperationsintermsofM,N,andd?
b.Ifd=2,whatistherunningtimeofallheapoperations?
c. Ifd=(N),whatisthetotalrunningtime?
d.Whatchoiceofdminimizesthetotalrunningtime?
6.16 Suppose that binary heaps s are e represented d using g explicit t links. . Givea simple
algorithmtofindthetreenodethatisatimplicitpositioni.
6.17 Supposethatbinaryheapsarerepresentedusingexplicitlinks.Considertheprob-
lemofmergingbinaryheap
lhs
with
rhs
.Assumebothheapsareperfectbinary
trees,containing2
l
−1and2
r
−1nodes,respectively.
a. GiveanO(logN)algorithmtomergethetwoheapsifl=r.
b.GiveanO(logN)algorithmtomergethetwoheapsif|lr|=1.
c. GiveanO(log
2
N)algorithmtomergethetwoheapsregardlessoflandr.
6.18 Amin-maxheapisadatastructurethatsupportsboth
deleteMin
and
deleteMax
in
O(logN)peroperation.Thestructureisidenticaltoabinaryheap,buttheheap-
orderpropertyisthatforanynode,X,atevendepth,theelementstoredatXis
smallerthantheparentbutlargerthanthegrandparent(wherethismakessense),
andforanynode,X,atodddepth,theelementstoredatXislargerthantheparent
butsmallerthanthegrandparent.SeeFigure6.58.
a. Howdowefindtheminimumandmaximumelements?
b.Giveanalgorithmtoinsertanewnodeintothemin-maxheap.
c. Giveanalgorithmtoperform
deleteMin
and
deleteMax
.
d.Canyoubuildamin-maxheapinlineartime?
e. Supposewewouldliketosupport
deleteMin
,
deleteMax
,and
merge
.Proposea
datastructuretosupportalloperationsinO(logN)time.
6
81
14
71
31
59
25
16
24
17
80
79
63
20
18
19
87
12
52
32
13
78
15
48
28
31
42
Figure6.58 Min-maxheap
VB.NET PowerPoint: Add Image to PowerPoint Document Slide/Page
of "AddPage", "InsertPage" and "DeletePage" to add, insert or delete any certain PowerPoint slide without & profession imaging controls, PDF document, tiff
drag and drop pdf into powerpoint; pdf to powerpoint slide
C# PDF Text Extract Library: extract text content from PDF file in
text content from source PDF document file for word processing, presentation and desktop How to C#: Extract Text Content from PDF File. Add necessary references
export pdf to powerpoint; converting pdf to powerpoint slides
286
Chapter6 PriorityQueues(Heaps)
2
11
5
12
17
18
8
15
4
9
18
31
21
11
10
6
Figure6.59 InputforExercises6.19and6.26
6.19 MergethetwoleftistheapsinFigure6.59.
6.20 Showtheresultofinsertingkeys1to15inorderintoaninitiallyemptyleftistheap.
6.21 Proveordisprove:Aperfectlybalancedtreeformsifkeys1to2
k
−1areinserted
inorderintoaninitiallyemptyleftistheap.
6.22 Giveanexampleofinputthatgeneratesthebestleftistheap.
6.23 a. Canleftistheapsefficientlysupport
decreaseKey
?
b.Whatchanges,ifany(ifpossible),arerequiredtodothis?
6.24 Onewaytodeletenodesfromaknownpositioninaleftistheapistousealazy
strategy.Todeleteanode,merelymarkitdeleted.Whena
findMin
or
deleteMin
is
performed,thereisapotentialproblemiftherootismarkeddeleted,sincethenthe
nodehastobeactuallydeletedandtherealminimumneedstobefound,which
mayinvolvedeletingothermarkednodes.Inthisstrategy,
remove
scostoneunit,
butthecostofa
deleteMin
or
findMin
dependsonthenumberofnodesthatare
markeddeleted.Supposethataftera
deleteMin
or
findMin
therearekfewermarked
nodesthanbeforetheoperation.
a. Showhowtoperformthe
deleteMin
inO(klogN)time.

b.Proposeanimplementation,withananalysistoshowthatthetimetoperform
the
deleteMin
isO(klog(2N/k)).
6.25 Wecanperform
buildHeap
inlineartimeforleftistheapsbyconsideringeachele-
mentasaone-nodeleftistheap,placingalltheseheapsonaqueue,andperforming
thefollowingstep:Untilonlyoneheapisonthequeue,dequeuetwoheaps,merge
them,andenqueuetheresult.
a. ProvethatthisalgorithmisO(N)intheworstcase.
b.Whymightthisalgorithmbepreferabletothealgorithmdescribedinthetext?
6.26 MergethetwoskewheapsinFigure6.59.
6.27 Showtheresultofinsertingkeys1to15inorderintoaskewheap.
6.28 Proveordisprove:Aperfectlybalancedtreeformsifthekeys1to2
k
−1areinserted
inorderintoaninitiallyemptyskewheap.
6.29 AskewheapofNelementscanbebuiltusingthestandardbinaryheapalgorithm.
CanweusethesamemergingstrategydescribedinExercise6.25forskewheaps
togetanO(N)runningtime?
6.30 Provethatabinomialtree,B
k
,hasbinomialtreesB
0
,B
1
,...,B
k−1
aschildrenofthe
root.
C# Create PDF from OpenOffice to convert odt, odp files to PDF in
In order to run the sample codes, the following steps would be necessary. Add necessary references: RasterEdge.XDoc.PDF.dll. RasterEdge.XDoc.PowerPoint.dll.
convert pdf slides to powerpoint; pdf to ppt converter online
VB.NET Create PDF from OpenOffice to convert odt, odp files to PDF
In order to run the sample codes, the following steps would be necessary. Add necessary references: RasterEdge.XDoc.PDF.dll. RasterEdge.XDoc.PowerPoint.dll.
pdf to ppt; changing pdf to powerpoint file
Exercises
287
13
23
24
65
51
12
21
24
65
14
26
16
18
4
2
15
18
29
55
11
Figure6.60 InputforExercise6.32
6.31 Provethatabinomialtreeofheightkhas
k
d
nodesatdepthd.
6.32 MergethetwobinomialqueuesinFigure6.60.
6.33 a. ShowthatN
insert
sintoaninitiallyemptybinomialqueuetakeO(N)timein
theworstcase.
b.GiveanalgorithmtobuildabinomialqueueofNelements,usingatmostN−1
comparisonsbetweenelements.
c. ProposeanalgorithmtoinsertMnodesintoabinomialqueueofNelementsin
O(M+logN)worst-casetime.Proveyourbound.
6.34 Writeanefficientroutinetoperform
insert
usingbinomialqueues.Donotcall
merge
.
6.35 Forthebinomialqueue
a. Modifythe
merge
routinetoterminatemergingiftherearenotreesleftinH
2
and
the
carry
treeis
nullptr
.
b.Modifythe
merge
sothatthesmallertreeisalwaysmergedintothelarger.

6.36 Supposeweextendbinomialqueuestoallowatmosttwotreesofthesameheight
perstructure.CanweobtainO(1)worst-casetimeforinsertionwhileretaining
O(logN)fortheotheroperations?
6.37 Supposeyouhaveanumberofboxes,eachofwhichcanholdtotalweightCand
itemsi
1
,i
2
,i
3
,...,i
N
,whichweighw
1
,w
2
,w
3
,...,w
N
,respectively.Theobjectis
topackalltheitemswithoutplacingmoreweightinanyboxthanitscapacityand
usingasfewboxesaspossible.Forinstance,ifC=5,andtheitemshaveweights
2,2,3,3,thenwecansolvetheproblemwithtwoboxes.
Ingeneral,thisproblemisveryhard,andnoefficientsolutionisknown.Write
programstoimplementefficientlythefollowingapproximationstrategies:
a. Placetheweightinthefirstboxforwhichitfits(creatinganewboxifthereis
noboxwithenoughroom).(Thisstrategyandallthatfollowwouldgivethree
boxes,whichissuboptimal.)
b.Placetheweightintheboxwiththemostroomforit.
c. Placetheweightinthemostfilledboxthatcanacceptitwithoutoverflowing.

d.Areanyofthesestrategiesenhancedbypresortingtheitemsbyweight?
288
Chapter6 PriorityQueues(Heaps)
6.38 Supposewewanttoaddthe
decreaseAllKeys(
)
operationtotheheaprepertoire.
Theresultofthisoperationisthatallkeysintheheaphavetheirvaluedecreased
byanamount.Fortheheapimplementationofyourchoice,explainthenec-
essarymodifications sothatallotheroperations retaintheirrunningtimesand
decreaseAllKeys
runsinO(1).
6.39 Whichofthetwoselectionalgorithmshasthebettertimebound?
6.40 Thestandardcopyconstructorand
makeEmpty
forleftistheapscanfailbecauseof
toomanyrecursivecalls.Althoughthiswastrueforbinarysearchtrees,itismore
problematicforleftistheaps,becausealeftistheapcanbeverydeep,evenwhileit
hasgoodworst-caseperformanceforbasicoperations.Thusthecopyconstructor
and
makeEmpty
needtobereimplementedtoavoiddeeprecursioninleftistheaps.
Dothisasfollows:
a. Reordertherecursiveroutinessothattherecursivecallto
t->left
followsthe
recursivecallto
t->right
.
b.Rewritetheroutinessothatthelast statementisarecursivecallontheleft
subtree.
c. Eliminatethetailrecursion.
d.Thesefunctionsarestillrecursive.Giveapreciseboundonthedepthofthe
remainingrecursion.
e. Explainhowtorewritethecopyconstructorand
makeEmpty
forskewheaps.
References
Thebinaryheapwasfirstdescribedin[28].Thelinear-timealgorithmforitsconstruction
isfrom[14].
Thefirstdescriptionofd-heapswasin[19].Recentresultssuggestthat4-heapsmay
improvebinaryheapsinsomecircumstances[22].LeftistheapswereinventedbyCrane
[11]anddescribedinKnuth[21].SkewheapsweredevelopedbySleatorandTarjan[24].
BinomialqueueswereinventedbyVuillemin[27];Brownprovidedadetailedanalysisand
empiricalstudyshowingthattheyperformwellinpractice[4],ifcarefullyimplemented.
Exercise6.7(b–c)istakenfrom[17].Exercise6.10(c)isfrom[6].Amethodforcon-
structingbinaryheapsthatusesabout1.52Ncomparisonsonaverageisdescribedin[23].
Lazydeletioninleftistheaps(Exercise6.24)isfrom[10].AsolutiontoExercise6.36can
befoundin[8].
Min-maxheaps(Exercise6.18)wereoriginallydescribedin[1].Amoreefficientimple-
mentation of the operations isgiven in [18] ] and d [25]. . Alternativerepresentations for
double-endedpriorityqueuesarethedeap and diamonddeque.Detailscanbefoundin
[5],[7],and[9].Solutionsto6.18(e)aregivenin[12]and[20].
A theoretically interesting priority queuerepresentation is theFibonacci heap [16],
which wewilldescribein Chapter11.TheFibonacciheapallowsalloperationstobe
performedinO(1)amortizedtime,exceptfordeletions,whichareO(logN).Relaxedheaps
[13]achieveidenticalboundsintheworstcase(withtheexceptionof
merge
).Thepro-
cedureof[3]achievesoptimalworst-caseboundsforalloperations.Anotherinteresting
implementationisthepairingheap[15],whichisdescribedinChapter12.Finally,priority
queuesthatworkwhenthedataconsistofsmallintegersaredescribedin[2]and[26].
References
289
1.M.D.Atkinson,J.R.Sack,N.Santoro,andT.Strothotte,“Min-MaxHeapsandGeneralized
PriorityQueues,”CommunicationsoftheACM,29(1986),996–1000.
2.J.D.Bright,“RangeRestrictedMergeablePriorityQueues,”InformationProcessingLetters,47
(1993),159–164.
3.G.S.Brodal,“Worst-CaseEfficientPriorityQueues,”ProceedingsoftheSeventhAnnualACM-
SIAMSymposiumonDiscreteAlgorithms(1996),52–58.
4.M.R.Brown,“ImplementationandAnalysisofBinomialQueueAlgorithms,”SIAMJournal
onComputing,7(1978),298–319.
5.S. Carlsson, , “The Deap—ADouble-Ended Heap to o Implement Double-EndedPriority
Queues,”InformationProcessingLetters,26(1987),33–36.
6.S.CarlssonandJ.Chen,“TheComplexityofHeaps,”ProceedingsoftheThirdSymposiumon
DiscreteAlgorithms(1992),393–402.
7.S.Carlsson,J.Chen,andT.Strothotte,“ANoteontheConstructionoftheDataStructure
‘Deap’,”InformationProcessingLetters,31(1989),315–317.
8.S. Carlsson,J.I.Munro,andP.V.Poblete,“AnImplicitBinomialQueuewithConstant
InsertionTime,” Proceedingsof First Scandinavian WorkshoponAlgorithmTheory (1988),
1–13.
9.S.C.ChangandM.W.Due,“DiamondDeque:ASimpleDataStructureforPriorityDeques,”
InformationProcessingLetters,46(1993),231–237.
10.D. Cheriton n and d R. E. . Tarjan, “Finding g Minimum Spanning Trees,” ” SIAM Journal on
Computing,5(1976),724–742.
11.C.A.Crane,“LinearListsandPriorityQueuesasBalancedBinaryTrees,”TechnicalReport
STAN-CS-72-259, Computer Science Department, Stanford University, Stanford, Calif.,
1972.
12.Y.DingandM.A.Weiss,“TheRelaxedMin-MaxHeap:AMergeableDouble-EndedPriority
Queue,”ActaInformatica,30(1993),215–231.
13.J.R.Driscoll,H.N.Gabow,R.Shrairman,andR.E.Tarjan,“RelaxedHeaps:AnAlternative
toFibonacciHeapswithApplicationstoParallelComputation,”CommunicationsoftheACM,
31(1988),1343–1354.
14.R.W.Floyd,“Algorithm245:Treesort3,”CommunicationsoftheACM,7(1964),701.
15.M.L.Fredman,R.Sedgewick,D.D.Sleator,andR.E.Tarjan,“ThePairingHeap:ANew
FormofSelf-adjustingHeap,”Algorithmica,1(1986),111–129.
16.M.L.FredmanandR.E.Tarjan,“FibonacciHeapsandTheirUsesinImprovedNetwork
OptimizationAlgorithms,”JournaloftheACM,34(1987),596–615.
17.G.H.GonnetandJ.I.Munro,“HeapsonHeaps,”SIAMJournalonComputing,15(1986),
964–971.
18.A.HashamandJ.R.Sack,“BoundsforMin-maxHeaps,”BIT,27(1987),315–323.
19.D. B.Johnson, “PriorityQueues withUpdateandFinding Minimum Spanning Trees,”
InformationProcessingLetters,4(1975),53–57.
20.C.M.KhoongandH.W.Leong,“Double-EndedBinomialQueues,”ProceedingsoftheFourth
AnnualInternationalSymposiumonAlgorithmsandComputation(1993),128–137.
21.D.E.Knuth,TheArtofComputerProgramming,Vol.3:SortingandSearching,2ded.,Addison-
Wesley,Reading,Mass.,1998.
22.A.LaMarcaandR.E.Ladner,“TheInfluenceofCachesonthePerformanceofSorting,”
Proceedings of the Eighth h Annual ACM-SIAM Symposium m on Discrete e Algorithms (1997),
370–379.
290
Chapter6 PriorityQueues(Heaps)
23.C.J.H.McDiarmidandB.A.Reed,“BuildingHeapsFast,”JournalofAlgorithms,10(1989),
352–365.
24.D. D. Sleator andR. E.Tarjan, “Self-adjustingHeaps,” SIAMJournalon Computing, 15
(1986),52–69.
25.T.Strothotte,P.Eriksson,andS.Vallner,“ANoteonConstructingMin-maxHeaps,”BIT,29
(1989),251–256.
26.P. vanEmde Boas,R.Kaas,andE.Zijlstra,“DesignandImplementationofanEfficient
PriorityQueue,”MathematicalSystemsTheory,10(1977),99–127.
27.J.Vuillemin,“ADataStructureforManipulatingPriorityQueues,”Communicationsofthe
ACM,21(1978),309–314.
28.J. W. J. Williams, “Algorithm m 232: Heapsort,” ” Communications of f the e ACM, 7 (1964),
347–348.
C H A P P T E R
7
Sorting
Inthischapter,wediscusstheproblemofsortinganarrayofelements.Tosimplifymatters,
wewillassumeinourexamplesthatthearraycontainsonlyintegers,althoughourcode
willonceagainallowmoregeneralobjects.Formostofthischapter,wewillalsoassume
thattheentiresortcanbedoneinmainmemory,sothatthenumberofelementsisrelatively
small(lessthanafewmillion).Sortsthatcannotbeperformedinmainmemoryandmust
bedoneondiskortapearealsoquiteimportant.Thistypeofsorting,knownasexternal
sorting,willbediscussedattheendofthechapter.
Ourinvestigationofinternalsortingwillshowthat...
ThereareseveraleasyalgorithmstosortinO(N
2
),suchasinsertionsort.
Thereisanalgorithm,Shellsort,thatisvery simpletocode,runs ino(N
2
),andis
efficientinpractice.
ThereareslightlymorecomplicatedO(NlogN)sortingalgorithms.
Anygeneral-purposesortingalgorithmrequires(NlogN)comparisons.
Therestofthischapterwilldescribeandanalyzethevarioussortingalgorithms.These
algorithmscontaininterestingandimportantideasforcodeoptimizationaswellasalgo-
rithmdesign.Sortingisalsoanexamplewheretheanalysiscanbepreciselyperformed.Be
forewarnedthatwhereappropriate,wewilldoasmuchanalysisaspossible.
7.1 Preliminaries
Thealgorithmswedescribewillallbeinterchangeable.Eachwillbepassedanarraycon-
tainingtheelements;weassumeallarraypositionscontaindatatobesorted.Wewill
assumethatNisthenumberofelementspassedtooursortingroutines.
Wewillalsoassumetheexistenceofthe“<”and“>”operators,whichcanbeused
toplaceaconsistentorderingontheinput.Besidestheassignmentoperator,thesearethe
onlyoperationsallowedontheinputdata.Sortingundertheseconditionsisknownas
comparison-basedsorting.
ThisinterfaceisnotthesameasintheSTLsortingalgorithms.IntheSTL,sortingis
accomplishedbyuseofthefunctiontemplate
sort
.Theparametersto
sort
representthe
startandendmarkerofa(rangeina)containerandanoptionalcomparator:
void sort( Iterator begin, Iterator end d );
void sort( Iterator begin, Iterator end, Comparator cmp p );
291
Documents you may be interested
Documents you may be interested