sorting - Heap sort pseudo code algorithm -

sorting - Heap sort pseudo code algorithm -

in heap sort algorithm

n=m k:= m div 2 downwards 0 downheap(k); repeat t:=a[0] a[0]:=a[n-1] a[n-1]:=t n— downheap(0); until n <= 0

can 1 please explain me done in lines

n=m k:= m div 2 downwards 0 downheap(k);

i think heap building process mean for k:= m div 2 downwards 0

also n number of items.so in array representation lastly element stored @ a[n-1]? why n> = 0. can't finish @ n>0.because first element gets automatically sorted?

n=m k:= m div 2 downwards 0 downheap(k);

in binary heap, half of nodes have no children. can build heap starting @ midpoint , sifting items down. you're doing here building heap bottom up. consider array of 5 items:

[5, 3, 2, 4, 1]

or, tree:

5 3 2 4 1

the length 5, want start @ index 2 (assume 1-based heap array). downheap, then, @ node labeled 3 , compare smallest child. since 1 smaller 3, swap items giving:

5 1 2 4 3

since reached leaf level, we're done item. move on first item, 5. it's smaller 1, swap items:

1 5 2 4 3

but item 5 still larger children, swap:

1 3 2 4 5

and we're done. have valid heap.

it's instructive hand (with pencil , paper) build larger heap--say 10 items. give understanding of how algorithm works.

for purposes of building heap in way, doesn't matter if array indexes start @ 0 or 1. if array 0-based, end making 1 phone call downheap, doesn't because node you're trying move downwards leaf node. it's inefficient (one phone call downheap), not harmful.

it important, however, if root node @ index 1, stop loop n > 0 rather n >= 0. in latter case, end adding bogus value heap , removing item that's supposed there.

algorithm sorting data-structures heap heapsort