Algorithms

Chapter6Heapsort
AssistantProfessor:ChingChiLin chingchi.lin@gmail.com
DepartmentofComputerScienceandEngineering NationalTaiwanOceanUniversity

Outline
` ` ` ` `

Heaps Maintainingtheheapproperty Buildingaheap Theheapsort algorithm Priorityqueues

Thepurposeofthischapter
`

Inthischapter,weintroducetheheapsort algorithm.
` ` `

withworstcase runningtimeO(nlgn) aninplacesortingalgorithm:onlyaconstantnumberofarray elementsarestoredoutsidetheinputarrayatanytime. thus,requireatmostO(1)additionalmemory

Wealsointroducethe heap datastructure.

` `

anusefuldatastructureforheapsort makesanefficientpriorityqueue

Heaps
`

The(Binary) heap datastructureisanarray objectthatcanbe viewedasanearlycompletebinarytree.

`

Abinarytreewithn nodesanddepthk iscomplete iff itsnodes correspondtothenodesnumberedfrom1ton inthefullbinary treeofdepthk.

1 2

16

14
4 5 6

10
7

1 3

3 10

4 8

5 7

6 9

7 3

8 2

9 4

10 1

8
8 9

7
10

16 14

Binarytreerepresentations

1 2 4 8 9 10 5 11 12 6 13 14 3 7 15 8 4 9 10 2 5

1 3 6 7

Afullbinarytree ofheight3.

Acompletebinarytreewith10nodes andheight3.

AttributesofaHeap
`

AnarrayAthatpresentsaheapwithtwoattributes:
` ` `

length[A]: thenumberofelementsinthearray. heapsize[A]: thenumberofelementsintheheapstoredwith arrayA. length[A] heapsize[A]

1 2

16

14
4 5 6

10
7

1 3

3 10

4 8

5 7

6 9

7 3

8 2

9 4

10 1

16 14

8
8 9

7
10

2
6

length[A]=heapsize[A]=10

Basicprocedures1/2
`

Ifacompletebinarytreewithn nodesisrepresented sequentially,thenforanynodewithindexi,1 i n,wehave

` ` ` `

A[1]istheroot ofthetree theparentPARENT(i)isat i/2 ifi 1 theleftchildLEFT(i)isat2i therightchildRIGHT(i)isat2i +1

1 2

16

14
4 5 6

10
7

1 3

3 10

4 8

5 7

6 9

7 3

8 2

9 4

10 1

16 14

8
8 9

7
10

2
7

Basicprocedures2/2
`

TheLEFT procedurecancompute2i inoneinstructionbysimply shiftingthebinaryrepresentationofi leftonebitposition. Similarly,theRIGHT procedurecanquicklycompute2i +1by shiftingthebinaryrepresentationofileftonebitpositionand addingina1astheloworderbit. ThePARENT procedurecancomputei/2 byshiftingirightone bitposition.

Heapproperties
`

Therearetwokindofbinaryheaps:maxheapsandminheaps.
`

Inamaxheap,themaxheapproperty isthatforeverynodei otherthantheroot,

` `

A[PARENT(i)] A[i] . thelargestelementinamaxheapisstoredattheroot thesubtree rootedatanodecontainsvaluesnolargerthanthat containedatthenodeitself

Inaminheap,theminheapproperty isthatforeverynodei otherthantheroot,

A[PARENT(i)] A[i] .
` `

thesmallestelementinaminheapisattheroot

thesubtree rootedatanodecontainsvaluesnosmallerthanthat containedatthenodeitself

Maxandminheaps
14 12 10 8 6 7 5 MaxHeaps 6 9 3 25 30

2 7 10 8 6 4 50 20

10 83 21

11

MinHeaps
10

Theheightofaheap
`

Theheight ofanodeinaheapisthenumberofedgesonthe longestsimpledownwardpathfromthenodetoaleaf,and theheightoftheheaptobetheheightoftheroot,thatis (lg n). Forexample:

` `

theheightofnode2is2 theheightoftheheapis3
2

16

14
4 5 6

10
7

8
8 9

7
10

11

Theremainder ofthischapter
`

Weshallpresentssomebasicproceduresintheremainder ofthischapter.
` ` ` `

TheMAXHEAPIFY procedure,whichrunsinO(lg n)time,isthe keytomaintainingthemaxheapproperty. TheBUILDMAXHEAP procedure,whichrunsinO(n)time, producesamaxheapfromanunorderedinputarray. TheHEAPSORT procedure,whichrunsinO(n lg n)time,sortsan arrayinplace. TheMAXHEAPINSERT,HEAPEXTRACTMAX,HEAPINCREASEKEY, andHEAPMAXIMUM procedures,whichruninO(lg n)time, allowtheheapdatastructuretobeusedasapriorityqueue.

12

Outline
` ` ` ` `

Heaps Maintainingtheheapproperty Buildingaheap Theheapsort algorithm Priorityqueues

13

TheMAXHEAPIFY procedure1/2
`

MAXHEAPIFY isanimportantsubroutineformanipulatingmax heaps.

` ` ` `

Input:anarrayAandanindexi Output:thesubtree rootedatindexi becomesamaxheap Assume:thebinarytreesrootedatLEFT(i) andRIGHT(i) are maxheaps,butA[i]maybesmallerthanitschildren Method:letthevalueatA[i]floatdown inthemaxheap
1 1 3 2

i
4

16

16

4
5 6

10
7

MAXHEAPIFY
4

14
5 6

10
7

14
8 9

7
10

3
8

8
9

7
10

2
14

TheMAXHEAPIFY procedure2/2
MAXHEAPIFY(A,i) 1. l LEFT(i)
2. 3. 4. 5. 6. 7. 8. 9. 10.

r RIGHT(i) if l heapsize[A]andA[l]>A[i] then largest l else largest i if r heapsize[A]anda[r]>A[largest] then largest r if largest i
A[largest] then exchangeA[i]

MAXHEAPIFY (A,largest)

15

AnexampleofMAXHEAPIFY procedure
1 2 1 3 2

16

16

i
4

4
5 6

10
7 4

14
5 6

10
7

14
8 9

7
10

i
8

4
9

7
10

1
1 2

16

14
4 5 6

10
7

8
8 9

7 i 1
10

2
16

Thetimecomplexity
` ` `

Ittakes(1)timetofixuptherelationshipsamongthe elementsA[i],A[LEFT(i)],andA[RIGHT(i)]. Also,weneedtorunMAXHEAPIFY onasubtree rootedatone ofthechildrenofnodei. Thechildrenssubtrees eachhavesizeatmost2n/3

`

worstcaseoccurswhenthelastrowofthetreeisexactlyhalffull

TherunningtimeofMAXHEAPIFY is T(n)=T(2n/3)+(1) = O(lg n)

`

solveitbycase2ofthemastertheorem

Alternatively,wecancharacterizetherunningtimeofMAX HEAPIFY onanodeofheighthasO(h).

17

Outline
` ` ` ` `

Heaps Maintainingtheheapproperty Buildingaheap Theheapsort algorithm Priorityqueues

18

BuildingaHeap
` ` `

WecanusetheMAXHEAPIFY proceduretoconvertanarray A=[1..n]intoamaxheapinabottomupmanner. Theelementsinthesubarray A[(n/2+1)n ]areallleaves of thetree,andsoeachisa1elementheap. TheprocedureBUILDMAXHEAP goesthroughtheremaining nodesofthetreeandrunsMAXHEAPIFY oneachone.
BUILDMAXHEAP(A)
1. 2. 3.

heapsize[A] length[A] for i length[A]/2 downto 1 do MAXHEAPIFY(A,i)

19

Anexample
1 A 4 2 1 3 3 4 2 5 16 6 9 7 10 8 14
1 2

9 8

10 7

1
4

i
9 10

2
8

16

10

14

20

[1] 4 [2] 1 [4] 2 14 [8] 8 [5] 16 7 [3] 3 9 [6] [9] [10] MAXHEAPIFY(A,5) 10 [7] [2] 1 [4] 2 14 [8] 8

[1] 4 [3] 3 9 [6] 7 [9] [10] MAXHEAPIFY(A,4) 10 [7] 2 [8] 8 [2] 1 [4] 14

[1] 4 [3] 3 9 [6] 7 [9] [10] MAXHEAPIFY(A,3) 10 [7]

[5] 16

[5] 16

MAXHEAPIFY(A,1) [1] 4 [2] 16 [4] 14 2 [8] 8 [5] 7 1 [3] 10 9 [6] [9] [10] 3 [7] 2 [8] 8 7 [9] [10] [2] 16 [4] 14 [5] 1 [1] 4 [3] 10 9 [6] 3 [7] 2 [8] 8

MAXHEAPIFY(A,2) [1] 4 [2] 1 [4] 14 [5] 16 7 [3] 10 9 [6] [9] [10] 3 [7]

[1] 16 [2] 4 [4] 14 2 [8] 8 [5] 7 1 [3] 10 9 [6] [9] [10] 3 [7] 2 [8] 8 [2] 14 [4] 4

[1] 16 [3] 10 9 [6] 1 [9] [10] 3 [7] 2 [8] 4 [2] 14 [4] 8

[1] 16 [3] 10 9 [6] 1 [9] [10] maxheap 3 [7]

[5] 7

[5] 7

Correctness1/2
`

ToshowwhyBUILDMAXHEAP workcorrectly,weusethe followingloopinvariant:

`

Atthestartofeachiterationoftheforloopoflines23,each nodei +1,i +2,,n istherootofamaxheap.

BUILDMAXHEAP(A)
1. 2. 3.

heapsize[A] length[A] for i length[A]/2 downto 1 do MAXHEAPIFY(A,i)

Weneedtoshowthat
` ` `
23

thisinvariantistruepriortothefirstloopiteration eachiterationoftheloopmaintainstheinvariant theinvariantprovidesausefulpropertytoshowcorrectness whentheloopterminates.

Correctness2/2
`

Initialization: Priortothefirstiterationoftheloop,i=n/2.
n/2+1,n isaleafandisthustherootofa

trivialmaxheap.
`

Maintenance:Bythe loopinvariant,thechildrenofnodei are

bothrootsofmaxheaps.Thisispreciselythe conditionrequiredforthecallMAXHEAPIFY(A,i) tomakenodei amaxheaproot.Moreover,the MAXHEAPIFY callpreservesthepropertythat nodesi+1,i+2,...,nareallrootsofmaxheaps.

Termination: Attermination,i =0.Bytheloopinvariant,eachnode

1,2,,n istherootofamaxheap. Inparticular,node1is.

24

Timecomplexity1/2
`

Analysis1:
` `

EachcalltoMAXHEAPIFY costsO(lg n),andthereareO(n)such calls. Thus,therunningtimeisO(n lg n).Thisupperbound,through correct,isnotasymptoticallytight. Forannelementheap,heightislg n andatmostn /2h+1 nodesofanyheighth. ThetimerequiredbyMAXHEAPIFY whencalledonanodeof heighth isO(h). lg n lg n h n Thetotalcostis h +1 O (h ) = O n h .
h =0

Analysis2:
` ` `

h =0

25

Timecomplexity2/2
`

Thelastsummationyields
1/ 2 h = =2 2 h (1 1 / 2) h =0 2

Thus,therunningtimeofBUILDMAXHEAP canbeboundedas
lg n

h =0

h n 2 h +1 O (h) = O n 2 h = O(n) h =0

Wecanbuildamaxheapfromanunorderedarrayinlinear time.

26

Outline
` ` ` ` `

Heaps Maintainingtheheapproperty Buildingaheap Theheapsort algorithm Priorityqueues

27

Theheapsort algorithm
` ` `

Sincethemaximumelementofthearrayisstoredattheroot, A[1]wecanexchange itwithA[n]. Ifwenowdiscard A[n],weobservethatA[1...(n 1)]caneasily bemadeintoamaxheap. ThechildrenoftherootA[1]remainmaxheaps,butthenew rootA[1]elementmayviolatethemaxheapproperty,sowe needtoreadjust themaxheap.ThatistocallMAXHEAPIFY(A,1).
HEAPSORT(A)
1. 2. 3. 4. 5. 28

BUILDMAXHEAP(A) for i length[A]downto 2

A[i] do exchangeA[1]

heapsize[A] heapsize[A]1 MAXHEAPIFY(A,1)

Anexample
1

16

14
4 5 6

10
7

8
8 9

10

1 A
29

2 2

3 3

4 4

5 7

6 8

7 9

8 10

9 14

10 16

[1] 16 [2] 14 [4] 8 2 [8] 4 [5] 7 1 Initialheap [3] 10 9 [6] [9] [10] 3 [7] 2 [8] 4 [2] 14 [4] 8

[1] 1 [3] 10 9 [6] 16 Exchange Heapsize=10 Sorted=[16] Exchange Heapsize=9 Sorted=[14,16] [1] 1 [3] 10 9 [6] 3 [7] 2 14 16 [8] [9] [10] [2] 8 [4] 4 [5] 7 [3] 10 9 [6] 3 [7] 2 1 [2] 8 [4] 4 [9] [10] 3 [7] 2 4 [2] 14 [4] 8

[1] 1 [3] 10 9 [6] 16 Discard Heapsize=9 Sorted=[16] Readjust Heapsize=9 Sorted=[16] [1] 14 [3] 10 9 [6] 16 [8] [9] [10] 3 [7] [8] [9] [10] 3 [7]

[5] 7

[5] 7

Discard Heapsize=8 Sorted=[14,16] [1] 1 [2] 8 [4] 4 2 14 [5] 7 16

[5] 7

[8] [9] [10]

[1] 10 [2] 8 [4] 4 2 14 [5] 7 16 [3] 9 1 [6] [8] [9] [10] Readjust Heapsize=8 Sorted=[14,16] Heapsize=3 Sorted=[4,7,8,9,10,14,16] [1] 3 [2] 2 [4] 4 10 14 [5] 7 16 [3] 1 8 [6] [8] [9] [10] 9 [7] 10 14 [2] 2 [4] 1 3 [7] 10 [8] 14 [2] 8 [4] 4

[1] 9 [3] 3 1 [6] 16 Heapsize=7 Sorted=[10,14,16] [9] [10] 2 [7] 10 14 [2] 7 [4] 4

[1] 8 [3] 3 1 [6] 16 [8] [9] [10] Heapsize=6 Sorted=[9,10,14,16] 9 [7]

[5] 7

[5] 2

Heapsize=4 Sorted=[7,8,9,10,14,16] [1] 4 [3] 3 8 [6] 16 [8] [9] [10] 9 [7] 10

Heapsize=5 Sorted=[8,9,10,14,16] [1] 7 [2] 4 [4] 1 14 [5] 2 16 [3] 3 8 [6] [8] [9] [10] 9 [7]

[5] 7

Timecomplexity
`

TheHEAPSORT proceduretakesO(n lg n) time

` `

thecalltoBUILDMAXHEAP takesO(n)time eachofthen 1callstoMAXHEAPIFY takesO(lg n)time

32

Outline
` ` ` ` `

Heaps Maintainingtheheapproperty Buildingaheap Theheapsort algorithm Priorityqueues

33

Heapimplementationofpriorityqueues
` ` ` `

Heapsefficientlyimplementpriorityqueues. Therearetwokindsofpriorityqueues:maxpriorityqueues andminpriorityqueues. Wewillfocushereonhowtoimplementmaxpriorityqueues, whichareinturnbasedonmaxheaps. Apriorityqueue isadatastructureformaintainingasetS of elements,eachwithanassociatedvaluecalledakey.

34

Priorityqueues
`

Amaxpriorityqueue supportsthefollowingoperations.
` ` `

INSERT(S,x): insertstheelementx intothesetS. MAXIMUM(S): returnstheelementofS withthelargestkey. EXTRACTMAX(S): removesandreturnstheelementofS with thelargestkey. INCREASEKEY(S,x,k):increasesvalueofelementxs keytothe newvaluek.Assumek xs currentkey value.

35

Findingthemaximumelement
` `

MAXIMUM(S): returnstheelementofS withthelargestkey. Gettingthemaximumelementiseasy:itstheroot.

HEAPMAXIMUM(A)
1.

returnA[1]

TherunningtimeofHEAPMAXIMUM is(1).

36

Extractingmaxelement
`

EXTRACTMAX(S):removesandreturnstheelementofS with thelargestkey. HEAPEXTRACTMAX(A)

1. 2. 3. 4. 5. 6. 7.

if heapsize[A]<1 thenerror heapunderflow max A[1] A[1] A[heapsize[A]] heapsize[A] heapsize[A] 1 MAXHEAPIFY(A,1) return max

` `

Analysis: constanttimeassignments+timeforMAXHEAPIFY. TherunningtimeofHEAPEXTRACTMAX isO(lg n).

37

Increasingkeyvalue
`

INCREASEKEY(S,x,k):increasesvalueofelementxs keytok. Assumek xs currentkeyvalue.

HEAPINCREASEKEY (A,i,key)
1. 2. 3. 4. 5. 6.

if key <A[i] thenerror newkeyissmallerthean currentkey A[i] key While i >1andA[PARENT(i)]<A[i]

A[PARENT(i)] do exchangeA[i]

i PARENT(i)

` `

Analysis: thepathtracedfromthenodeupdatedtotheroot haslengthO(lg n). TherunningtimeisO(lg n).

38

Anexampleofincreasingkeyvalue
1

16

14
4 5 6

10
7

8
8

7
9 10

i
2

4 15

IncreaseKey!

39

[1] 16 [2] 14 [4] 8 i 2 [8] 4 1 [9] [10] [5] 7 [3] 10 9 [6] 3 [7] 2 [8] 15 [2] 14 [4] 8 i

[1] 16 [3] 10 9 [6] 1 3 [7]

[5] 7

[9] [10]

i [2] 15 [4] 14 2 [8] 8

[1] 16 [3] 10 9 [6] 1 3 [7] 2 [8] 8 i [2] 14

[1] 16 [3] 10 9 [6] 1 [9] [10] 3 [7]

[5] 7

[4] 15

[5] 7

[9] [10]

Insertingintotheheap
`

INSERT(S,x): insertstheelementx intothesetS.

MAXHEAPINSERT(A)
1. 2. 3.

heapsize[A] heapsize[A]+1 A[heapsize[A]

HEAPINCREASEKEY(A,heapsize[A],key)

` `

Analysis: constanttimeassignments+timeforHEAPINCREASEKEY. TherunningtimeisO(lg n).

41