252
Chapter6 PriorityQueues(Heaps)
14
14
16
19
19
19
68
65
26
32
21
21
16
19
68
65
26
32
31
31
Figure6.10 NexttwostepsindeleteMin
14
14
16
19
19
19
68
65
32
21
21
26
26
16
19
68
65
32
31
31
Figure6.11 LasttwostepsindeleteMin
makesurenottoassumethattherearealwaystwochildren,sothisusuallyinvolvesanextra
test.InthecodedepictedinFigure6.12,we’vedonethistestatline40.Oneextremely
trickysolutionisalwaystoensurethatyouralgorithmthinkseverynodehastwochildren.
Dothisbyplacingasentinel,ofvaluehigherthananyintheheap,atthespotaftertheheap
ends,atthestartofeachpercolatedownwhentheheapsizeiseven.Youshouldthinkvery
carefullybeforeattemptingthis,andyoumustputinaprominentcommentifyoudouse
thistechnique.Althoughthiseliminatestheneedtotestforthepresenceofarightchild,
youcannoteliminatetherequirementthatyoutestwhenyoureachthebottom,because
thiswouldrequireasentinelforeveryleaf.
Theworst-caserunningtimeforthisoperationisO(logN).Onaverage,theelement
thatisplacedattherootispercolatedalmosttothebottomoftheheap(whichisthelevel
itcamefrom),sotheaveragerunningtimeisO(logN).
6.3.4 OtherHeapOperations
Noticethat althoughfindingtheminimumcanbeperformedinconstant time,aheap
designedtofindtheminimumelement(alsoknownasa(min)heap)isofnohelpwhatso-
everinfindingthemaximumelement.Infact,aheaphasverylittleorderinginformation,
Embed pdf into powerpoint - 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
image from pdf to ppt; chart from pdf to powerpoint
Embed pdf into powerpoint - 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
convert pdf file to powerpoint; how to convert pdf to powerpoint slides
1
/**
2
* Remove the minimum item.
3
* Throws UnderflowException if empty.
4
*/
5
void deleteMin( )
6
{
7
if( isEmpty( ( ) ) )
8
throw UnderflowException{ { };
9
10
array[ 1 ] = = std::move( array[ [ currentSize-- ] );
11
percolateDown( 1 );
12
}
13
14
/**
15
* Remove the minimum item and d place e it in minItem.
16
* Throws UnderflowException if empty.
17
*/
18
void deleteMin( Comparable & minItem )
19
{
20
if( isEmpty( ( ) ) )
21
throw UnderflowException{ { };
22
23
minItem = = std::move( ( array[ [ 1 ] ] );
24
array[ 1 ] = = std::move( array[ [ currentSize-- ] );
25
percolateDown( 1 );
26
}
27
28
/**
29
* Internal l method d to percolate down in the e heap.
30
* hole is the index at which the percolate e begins.
31
*/
32
void percolateDown( ( int t hole )
33
{
34
int child;
35
Comparable tmp = std::move( array[ [ hole ] ] );
36
37
for( ; ; hole * 2 2 <= = currentSize; ; hole e = child )
38
{
39
child = = hole * 2;
40
if( child d != currentSize e && array[ [ child + 1 ] ] < < array[ child ] ] )
41
++child;
42
if( array[ [ child d ] ] < tmp )
43
array[ hole ] = = std::move( array[ [ child ] );
44
else
45
break;
46
}
47
array[ hole ] = = std::move( tmp p );
48
}
Figure6.12 MethodtoperformdeleteMininabinaryheap
C# PDF Convert to HTML SDK: Convert PDF to html files in C#.net
Embed PDF hyperlinks to HTML links. also makes PDF document visible and searchable on the Internet by converting PDF document file into HTML webpage.
how to convert pdf to powerpoint; convert pdf into ppt online
C# TIFF: How to Embed, Remove, Add and Update TIFF Color Profile
On the whole, our SDK supports the following manipulations. Empower C# programmers to embed, remove, add and update ICCProfile. Support
convert pdf file to powerpoint online; how to add pdf to powerpoint
254
Chapter6 PriorityQueues(Heaps)
Figure6.13 Averylargecompletebinarytree
sothereisnowaytofindanyparticularelementwithoutalinearscanthroughtheentire
heap. To see this, consider the large heap p structure(theelements are not shown)in
Figure6.13,whereweseethattheonlyinformationknownaboutthemaximumelement
isthatitisatoneoftheleaves.Halftheelements,though,arecontainedinleaves,sothisis
practicallyuselessinformation.Forthisreason,ifitisimportanttoknowwhereelements
are,someotherdatastructure,suchasahashtable,mustbeusedinadditiontotheheap.
(Recallthatthemodeldoesnotallowlookinginsidetheheap.)
Ifweassumethat thepositionofeveryelement isknown bysomeothermethod,
thenseveralotheroperationsbecomecheap.Thefirstthreeoperationsbelowallrunin
logarithmicworst-casetime.
decreaseKey
The
decreaseKey(p,
)
operationlowersthevalueoftheitematposition
p
byapositive
amount.Sincethismightviolatetheheaporder,itmustbefixedbyapercolateup.This
operationcouldbeusefultosystemadministrators:Theycanmaketheirprogramsrun
withhighestpriority.
increaseKey
The
increaseKey(p,
)
operationincreasesthevalueoftheitematposition
p
byapositive
amount.Thisisdonewithapercolatedown.Manyschedulersautomaticallydropthe
priorityofaprocessthatisconsumingexcessive
CPU
time.
remove
The
remove(p)
operationremovesthenodeatposition
p
fromtheheap.Thisisdoneby
first performing
decreaseKey(p,
)
and then performing
deleteMin()
.When a process
VB.NET PDF Convert to HTML SDK: Convert PDF to html files in vb.
Turn PDF images to HTML images in VB.NET. Embed PDF hyperlinks to HTML links in VB.NET. Available zoom setting (fit page, fit width).
image from pdf to powerpoint; adding pdf to powerpoint
VB.NET PDF Convert to Images SDK: Convert PDF to png, gif images
Embed PDF to image converter in viewer. Quick evaluation source codes for VB.NET class. Sometimes, to convert PDF document into BMP, GIF, JPEG and PNG
convert pdf pages into powerpoint slides; pdf page to powerpoint
6.3 BinaryHeap
255
is terminated by a user(instead offinishing normally), it must beremovedfromthe
priorityqueue.
buildHeap
Thebinaryheapissometimesconstructedfromaninitialcollectionofitems.Thiscon-
structortakesas input items and places themintoa heap. Obviously, this can be
donewithNsuccessive
insert
s.Sinceeach
insert
willtakeO(1)averageandO(logN)
worst-case time,the totalrunning timeofthis algorithmwouldbe O(N)averagebut
O(NlogN)worst-case.Sincethisisaspecialinstructionandtherearenootheroperations
intervening,andwealreadyknowthattheinstructioncanbeperformedinlinearaver-
agetime,itisreasonabletoexpectthatwithreasonablecarealineartimeboundcanbe
guaranteed.
ThegeneralalgorithmistoplacetheNitemsintothetreeinanyorder,maintainingthe
structureproperty.Then,if
percolateDown(i)
percolatesdownfromnode
i
,the
buildHeap
routineinFigure6.14canbeusedbytheconstructortocreateaheap-orderedtree.
The first tree in n Figure e 6.15 is the unordered tree.The seven remaining trees in
Figures 6.15 through 6.18 show the resultofeach ofthe seven
percolateDown
s.Each
dashed linecorrespondstotwocomparisons:onetofindthesmallerchildandoneto
compare thesmallerchild with thenode.Notice that there areonly 10dashed lines
in theentirealgorithm(therecouldhavebeen an 11th—where?)corresponding to20
comparisons.
Toboundtherunningtimeof
buildHeap
,wemustboundthenumberofdashedlines.
This can be done bycomputingthesumof theheights of allthenodes in theheap,
whichisthemaximumnumberofdashedlines.Whatwewouldliketoshowisthatthis
sumisO(N).
1
explicit BinaryHeap( ( const vector<Comparable> & items )
2
: array( items.size( ) ) + + 10 ), currentSize{ items.size( ( ) ) }
3
{
4
for( int t i = = 0; i i < items.size( ( ); ++i i )
5
array[ i i + + 1 ] = = items[ [ i ];
6
buildHeap( );
7
}
8
9
/**
10
* Establish heap order property from an arbitrary
11
* arrangement of items. . Runs s in linear time.
12
*/
13
void buildHeap( )
14
{
15
for( int t i = = currentSize e / / 2; ; i i > > 0; --i )
16
percolateDown( i i );
17
}
Figure6.14 buildHeapandconstructor
C# Raster - Image Save Options in C#.NET
NET Read: PDF Image Extract; VB.NET Write: Insert text into PDF; VB.NET How-to, VB.NET PDF, VB.NET Word, VB a zone bit of whether it's need to embed Color profile
how to change pdf to powerpoint on; change pdf to powerpoint online
C# TIFF: How to Insert & Burn Picture/Image into TIFF Document
Entire C# Code to Embed and Burn Image to TIFF GetPage(0); // load an PNG logo into REImage REImage powerful & profession imaging controls, PDF document, tiff
add pdf to powerpoint presentation; convert pdf file to ppt online
256
Chapter6 PriorityQueues(Heaps)
150
80
40
30
10
70
110
100
20
90
60
50
120
140
130
150
80
40
30
10
70
110
100
20
90
60
50
120
140
130
Figure6.15 Left:initialheap;right:afterpercolateDown(7)
150
80
40
30
10
50
110
100
20
90
60
70
120
140
130
150
80
40
30
10
50
110
100
20
90
60
70
120
140
130
Figure6.16 Left:afterpercolateDown(6);right:afterpercolateDown(5)
150
80
40
20
10
50
110
100
30
90
60
70
120
140
130
150
80
40
20
10
50
110
100
30
90
60
70
120
140
130
Figure6.17 Left:afterpercolateDown(4);right:afterpercolateDown(3)
Theorem6.1
Fortheperfectbinarytreeofheighthcontaining2
h+1
−1nodes,thesumoftheheights
ofthenodesis2h+1−1−(h+1).
Proof
Itiseasytoseethatthistreeconsistsof1nodeatheighth,2nodesatheighth−1,22
nodesatheighth−2,andingeneral2
i
nodesatheighthi.Thesumoftheheights
ofallthenodesisthen
VB.NET TIFF: Rotate TIFF Page by Using RaterEdge .NET TIFF
formats are: JPEG, PNG, GIF, BMP, PDF, Word (Docx Visual Basic .NET class, and then embed "RasterEdge.Imaging splitting huge target TIFF file into multiple and
converting pdf to ppt; how to convert pdf into powerpoint
VB.NET Image: How to Draw and Cutomize Text Annotation on Image
NET text annotation add-on tutorial can be divided into a few on document files in VB.NET, including PDF, TIFF & license and at last you can embed the required
convert pdf slides to powerpoint; convert pdf to ppt online without email
6.4 ApplicationsofPriorityQueues
257
150
10
40
20
60
50
110
100
30
90
80
70
120
140
130
10
20
40
30
60
50
110
100
150
90
80
70
120
140
130
Figure6.18 Left:afterpercolateDown(2);right:afterpercolateDown(1)
S=
h
i=0
2
i
(hi)
=h+2(h−1)+4(h−2)+8(h−3)+16(h−4)+···+2
h−1
(1)
(6.1)
Multiplyingby2givestheequation
2S=2h+4(h−1)+8(h−2)+16(h−3)+···+2
h
(1)
(6.2)
WesubtractthesetwoequationsandobtainEquation(6.3).Wefindthatcertainterms
almostcancel.Forinstance,wehave2h−2(h−1)=2,4(h−1)−4(h−2)=4,and
soon.ThelastterminEquation(6.2),2h,doesnotappearinEquation(6.1);thus,
itappearsinEquation(6.3).ThefirstterminEquation(6.1),h,doesnotappearin
Equation(6.2);thus,−happearsinEquation(6.3).Weobtain
S=−h+2+4+8+···+2
h−1
+2
h
=(2
h+1
−1)−(h+1)
(6.3)
whichprovesthetheorem.
Acompletetreeisnotaperfectbinarytree,buttheresultwehaveobtainedisanupper
boundonthesumoftheheightsofthenodesinacompletetree.Sinceacompletetreehas
between2
h
and2
h+1
nodes,thistheoremimpliesthatthissumisO(N),whereNisthe
numberofnodes.
Althoughtheresultwehaveobtainedissufficienttoshowthat
buildHeap
islinear,the
boundonthesumoftheheightsisnotasstrongaspossible.Foracompletetreewith
= 2nodes,theboundwehaveobtainedisroughly2N.Thesumoftheheightscan
beshown byinductiontobeNb(N),whereb(N)isthenumberof1sinthebinary
representationofN.
6.4 ApplicationsofPriorityQueues
Wehavealreadymentionedhowpriorityqueuesareusedinoperatingsystemsdesign.
InChapter9,wewillseehowpriorityqueuesareusedtoimplementseveralgraphalgo-
rithmsefficiently.Herewewillshowhowtousepriorityqueuestoobtainsolutionstotwo
problems.
VB.NET Image: VB.NET Code to Add Rubber Stamp Annotation to Image
Suitable for VB.NET PDF, Word & TIFF document managing & editing project. VB Can be implemented into both Windows and web VB.NET applications; Support single or
converting pdf to powerpoint; how to convert pdf into powerpoint on
VB.NET Image: Creating Hotspot Annotation for Visual Basic .NET
the configuration environment to integrate RasterEdge Visual Basic .NET into your imaging to provide powerful & profession imaging controls, PDF document, tiff
how to convert pdf into powerpoint presentation; how to convert pdf to ppt online
258
Chapter6 PriorityQueues(Heaps)
6.4.1 TheSelectionProblem
ThefirstproblemwewillexamineistheselectionproblemfromSection1.1.Recallthatthe
inputisalistofNelements,whichcanbetotallyordered,andanintegerk.Theselection
problemistofindthekthlargestelement.
TwoalgorithmsweregiveninChapter1,butneitherisveryefficient.Thefirstalgo-
rithm,whichweshallcallalgorithm1A,istoreadtheelementsintoanarrayandsortthem,
returningtheappropriateelement.Assumingasimplesortingalgorithm,therunningtime
isO(N
2
).Thealternativealgorithm,1B,istoreadkelementsintoanarrayandsortthem.
Thesmallestoftheseisinthekthposition.Weprocesstheremainingelementsonebyone.
Asanelementarrives,itiscomparedwiththekthelementinthearray.Ifitislarger,then
thekthelementisremoved,andthenewelementisplacedinthecorrectplaceamongthe
remainingk−1elements.Whenthealgorithmends,theelementinthekthpositionisthe
answer.TherunningtimeisO(N·k)(why?).Ifk=N/2,thenbothalgorithmsareO(N
2
).
Noticethatforanyk,wecansolvethesymmetricproblemoffindingthe(Nk+1)th
smallestelement,sok= N/2isreallythehardestcaseforthesealgorithms.Thisalso
happenstobethemostinterestingcase,sincethisvalueofkisknownasthemedian.
Wegivetwoalgorithmshere,bothofwhichruninO(NlogN)intheextremecaseof
k=N/2,whichisadistinctimprovement.
Algorithm6A
Forsimplicity,weassumethat weareinterested d in n finding g thekth smallest element.
The algorithm is simple. We read the elements into an n array. We e then apply the
buildHeap
algorithmtothisarray.Finally,weperformk
deleteMin
operations.Thelast
elementextractedfromtheheapisouranswer.Itshouldbeclearthatbychangingthe
heap-orderproperty,wecouldsolvetheoriginalproblemoffindingthekthlargestelement.
Thecorrectnessofthealgorithmshouldbeclear.Theworst-casetimingisO(N)to
constructtheheap,if
buildHeap
isused,andO(logN)foreach
deleteMin
.Sincetherearek
deleteMin
s,weobtainatotalrunningtimeofO(N+klogN).Ifk=O(N/logN),thenthe
runningtimeisdominatedbythe
buildHeap
operationandisO(N).Forlargervaluesofk,
therunningtimeisO(klogN).Ifk=N/2,thentherunningtimeis(NlogN).
Noticethatifwerunthisprogramfork=Nandrecordthevaluesastheyleavethe
heap,wewillhaveessentiallysortedtheinputfileinO(NlogN)time.InChapter7,we
willrefinethisideatoobtainafastsortingalgorithmknownasheapsort.
Algorithm6B
Forthesecondalgorithm,wereturntotheoriginalproblemandfindthekthlargestele-
ment.Weusetheideafromalgorithm1B.AtanypointintimewewillmaintainasetS
oftheklargestelements.Afterthefirstkelementsareread,whenanewelementisread
itiscomparedwiththekthlargestelement,whichwedenotebyS
k
.NoticethatS
k
isthe
smallestelementinS.Ifthenewelementislarger,thenitreplacesS
k
inS.Swillthenhave
anewsmallestelement,whichmayormaynotbethenewlyaddedelement.Attheendof
theinput,wefindthesmallestelementinSandreturnitastheanswer.
ThisisessentiallythesamealgorithmdescribedinChapter1.Here,however,wewill
useaheaptoimplementS.ThefirstkelementsareplacedintotheheapintotaltimeO(k)
withacallto
buildHeap
.ThetimetoprocesseachoftheremainingelementsisO(1),totest
6.4 ApplicationsofPriorityQueues
259
iftheelementgoesintoS,plusO(logk),todeleteS
k
andinsertthenewelementifthisis
necessary.Thus,thetotaltimeisO(k+(Nk)logk)= O(Nlogk).Thisalgorithmalso
givesaboundof(NlogN)forfindingthemedian.
In Chapter 7, we e will see e how to solve e this problem m in O(N) average e time. In
Chapter10,wewillseeanelegant,albeitimpractical,algorithmtosolvethis problem
inO(N)worst-casetime.
6.4.2 EventSimulation
InSection3.7.3,wedescribedanimportantqueuingproblem.Recallthatwehaveasys-
tem,suchasabank,wherecustomersarriveandwaitinalineuntiloneofktellersis
available.Customerarrivalisgovernedbyaprobabilitydistributionfunction,asistheser-
vicetime(theamountoftimetobeservedonceatellerisavailable).Weareinterested
in statisticssuchashowlongon averageacustomerhastowait orhowlong theline
mightbe.
Withcertainprobabilitydistributionsandvaluesofk,theseanswerscanbecomputed
exactly.However,askgetslarger,theanalysisbecomesconsiderablymoredifficult,soitis
appealingtouseacomputertosimulatetheoperationofthebank.Inthisway,thebank
officerscandeterminehowmanytellersareneededtoensurereasonablysmoothservice.
Asimulation consistsofprocessingevents.Thetwoeventshereare(a)acustomer
arrivingand(b)acustomerdeparting,thusfreeingupateller.
Wecanusetheprobabilityfunctionstogenerateaninputstreamconsistingofordered
pairsofarrivaltimeandservicetimeforeachcustomer,sortedbyarrivaltime.Wedonot
needtousetheexacttimeofday.Rather,wecanuseaquantumunit,whichwewillrefer
toasatick.
Onewaytodothissimulationistostartasimulationclockatzeroticks.Wethen
advancetheclockonetickatatime,checkingtoseeifthereisanevent.Ifthereis,thenwe
processtheevent(s)andcompilestatistics.Whentherearenocustomersleftintheinput
streamandallthetellersarefree,thenthesimulationisover.
Theproblemwiththissimulationstrategyisthatitsrunningtimedoesnotdepend
onthenumberofcustomersorevents(therearetwoeventspercustomer),butinstead
dependsonthenumberofticks,whichisnotreallypartoftheinput.Toseewhythisis
important,supposewechangedtheclockunitstomilliticksandmultipliedallthetimes
intheinputby1,000.Theresultwouldbethatthesimulationwouldtake1,000times
longer!
Thekeytoavoidingthisproblemistoadvancetheclocktothenexteventtimeateach
stage.Thisisconceptuallyeasytodo.Atanypoint,thenexteventthatcanoccuriseither
(a)thenextcustomerintheinputfilearrivesor(b)oneofthecustomersatatellerleaves.
Sinceallthetimeswhentheeventswillhappenareavailable,wejustneedtofindtheevent
thathappensnearestinthefutureandprocessthatevent.
Iftheeventisadeparture,processingincludesgatheringstatisticsforthedeparting
customerandcheckingtheline(queue)toseewhetherthereisanothercustomerwaiting.
Ifso,weaddthatcustomer,processwhateverstatisticsarerequired,computethetime
when that customerwillleave,andaddthat departuretothe set ofeventswaiting to
happen.
260
Chapter6 PriorityQueues(Heaps)
Iftheeventisanarrival,wecheckforanavailableteller.Ifthereisnone,weplacethe
arrivalontheline(queue);otherwisewegivethecustomerateller,computethecustomer’s
departuretime,andaddthedeparturetothesetofeventswaitingtohappen.
Thewaitinglineforcustomerscanbeimplementedasaqueue.Sinceweneedtofind
theeventnearestinthefuture,itisappropriatethatthesetofdepartureswaitingtohappen
beorganizedinapriorityqueue.Thenexteventisthusthenextarrivalornextdeparture
(whicheverissooner);bothareeasilyavailable.
Itisthenstraightforward,althoughpossiblytime-consuming,towritethesimulation
routines.IfthereareCcustomers(andthus2Cevents)andktellers,thentherunningtime
ofthesimulationwouldbeO(Clog(k+1))becausecomputingandprocessingeachevent
takesO(logH),whereH=k+1isthesizeoftheheap.
3
6.5 d-Heaps
Binaryheapsaresosimplethattheyarealmostalwaysusedwhenpriority queuesare
needed.Asimplegeneralizationisad-heap,whichisexactlylikeabinaryheapexceptthat
allnodeshavedchildren(thus,abinaryheapisa2-heap).
Figure6.19showsa3-heap.Noticethatad-heapismuchshallowerthanabinaryheap,
improvingtherunningtimeof
insert
stoO(log
d
N).However,forlarged,the
deleteMin
operationismoreexpensive,becauseeventhoughthetreeisshallower,theminimumofd
childrenmustbefound,whichtakesd−1comparisonsusingastandardalgorithm.This
raisesthetimeforthisoperationtoO(dlog
d
N).Ifdisaconstant,bothrunningtimesare,of
course,O(logN).Althoughanarraycanstillbeused,themultiplicationsanddivisionsto
findchildrenandparentsarenowbyd,which,unlessdisapowerof2,seriouslyincreases
therunningtime,becausewecannolongerimplementdivisionbyabitshift.d-heapsare
interestingintheory,becausetherearemanyalgorithmswherethenumberofinsertionsis
muchgreaterthanthenumberof
deleteMin
s(andthusatheoreticalspeedupispossible).
Theyarealsoofinterestwhenthepriorityqueueistoolargetofitentirelyinmainmemory.
1
10
11
9
13
15
17
4
7
6
8
9
5
3
2
Figure6.19 Ad-heap(d=3)
3
WeuseO(Clog(k+1))insteadofO(Clogk)toavoidconfusionforthek=1case.
6.6 LeftistHeaps
261
Inthiscase,ad-heapcanbeadvantageousinmuchthesamewayasB-trees.Finally,there
isevidencesuggestingthat4-heapsmayoutperformbinaryheapsinpractice.
Themostglaringweaknessoftheheapimplementation,asidefromtheinabilitytoper-
form
find
s,isthatcombiningtwoheapsintooneisahardoperation.Thisextraoperation
isknownasa
merge
.Therearequiteafewwaystoimplementheapssothattherunning
timeofa
merge
isO(logN).Wewillnowdiscussthreedatastructures,ofvariouscomplex-
ity,thatsupportthe
merge
operationefficiently.Wewilldeferanycomplicatedanalysisuntil
Chapter11.
6.6 LeftistHeaps
Itseemsdifficulttodesignadatastructurethatefficientlysupportsmerging(thatis,pro-
cessesa
merge
ino(N)time)andusesonlyanarray,asinabinaryheap.Thereasonfor
thisisthatmergingwouldseemtorequirecopyingonearrayintoanother,whichwould
take(N)timeforequal-sizedheaps.Forthisreason,alltheadvanceddatastructuresthat
supportefficientmergingrequiretheuseofalinkeddatastructure.Inpractice,wecan
expectthatthiswillmakealltheotheroperationsslower.
Likeabinaryheap,aleftistheaphasbothastructuralpropertyandanorderingprop-
erty.Indeed,aleftistheap,likevirtuallyallheapsused,hasthesameheap-orderproperty
wehavealreadyseen.Furthermore,aleftistheapisalsoabinarytree.Theonlydifference
betweenaleftistheapandabinaryheapisthatleftistheapsarenotperfectlybalanced,but
actuallyattempttobeveryunbalanced.
6.6.1 LeftistHeapProperty
Wedefinethenullpathlength,npl(X),ofanynodeXtobethelengthoftheshortestpath
fromXtoanodewithouttwochildren.Thus,thenplofanodewithzerooronechildis
0,whilenpl
(nullptr)
=−1.InthetreeinFigure6.20,thenullpathlengthsareindicated
insidethetreenodes.
Noticethatthenullpathlengthofanynodeis1morethantheminimumofthenull
pathlengthsofitschildren.Thisappliestonodeswithlessthantwochildrenbecausethe
nullpathlengthof
nullptr
is−1.
TheleftistheappropertyisthatforeverynodeXintheheap,thenullpathlengthof
theleftchildisatleastaslargeasthatoftherightchild.Thispropertyissatisfiedbyonly
oneofthetreesinFigure6.20,namely,thetreeontheleft.Thispropertyactuallygoes
outofitswaytoensurethatthetreeisunbalanced,becauseitclearlybiasesthetreetoget
deeptowardtheleft.Indeed,atreeconsistingofalongpathofleftnodesispossible(and
actuallypreferabletofacilitatemerging)—hencethenameleftistheap.
Becauseleftistheapstendtohavedeepleftpaths,itfollowsthattherightpathought
tobeshort.Indeed,therightpath downaleftist heapisasshortasanyintheheap.
Otherwise,therewouldbeapaththatgoesthroughsomenodeXandtakestheleftchild.
ThenXwouldviolatetheleftistproperty.
Theorem6.2
Aleftisttreewithrnodesontherightpathmusthaveatleast2
r
−1nodes.
Documents you may be interested
Documents you may be interested