Heap sort pseudo code algorithm

Question

In heap sort algorithm

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

Can some one please explain to me what is done in lines

    n=m
    for k:= m div 2 down to 0
        downheap(k);  

I think that is the heap building process but what is mean by for k:= m div 2 down to 0

Also is n the number of items.So in an array representation last element is stored at a[n-1]? But why do it for n> = 0. Can't we finish at n>0.Because the first element gets automatically sorted?

Answer 1

for k:= m div 2 down to 0

This appears to be pseudocode for:

for(int k = m/2; k >= 0; k--)

Or possibly

for(int k = m/2; k > 0; k--)

Depending on whether "down to 0" is inclusive or not.

Also is n the number of items?

Initially, yes, but it decrements on the line n-.

Can't we finish at n>0.Because the first element gets automatically sorted?

Yes, this is effectively what happens. Once N becomes zero at n-, it's most of the way through the loop body, so the only thing that gets executed after that and before until n <= 0 terminates is downheap(0);

Answer 2

n=m
for k:= m div 2 down to 0
    downheap(k);

In a binary heap, half of the nodes have no children. So you can build a heap by starting at the midpoint and sifting items down. What you're doing here is building the heap from the bottom up. Consider this array of five items:

[5, 3, 2, 4, 1]

Or, as a tree:

     5
  3     2
4   1

The length is 5, so we want to start at index 2 (assume a 1-based heap array). downheap, then, will look at the node labeled 3 and compare it with the smallest child. Since 1 is smaller than 3, we swap the items giving:

     5
  1     2
4   3

Since we reached a leaf level, we're done with that item. Move on to the first item, 5. It's smaller than 1, so we swap items:

     1
  5     2
4   3

But the item 5 is still larger than its children, so we do another swap:

     1
  3     2
4   5

And we're done. You have a valid heap.

It's instructive to do that by hand (with pencil and paper) to build a larger heap--say 10 items. That will give you a very good understanding of how the algorithm works.

For purposes of building the heap in this way, it doesn't matter if the array indexes start at 0 or 1. If the array is 0-based, then you end up making one extra call to downheap, but that doesn't do anything because the node you're trying to move down is already a leaf node. So it's slightly inefficient (one extra call to downheap), but not harmful.

It is important, however, that if your root node is at index 1, that you stop your loop with n > 0 rather than n >= 0. In the latter case, you could very well end up adding a bogus value to your heap and removing an item that's supposed to be there.