Analysis of Algorithms : An Active Learning Approach

3.5 HEAPSORT 79

key the key value that needs to be reinserted in the heap
bound the upper limit (index) on the heap

vacant = root
while 2vacant ≤ bound do
largerChild = 2vacant

// find the larger of the two children
if (largerChild < bound) and (list[largerChild+1] > list[largerChild]) then
largerChild = largerChild + 1
end if

// does the key belong above this child?
if key > list[ largerChild ] then
// yes, stop looping
break
else
// no, move the larger child up
list[ vacant ] = list[ largerChild ]
vacant = largerChild
end if
end while
list[ vacant ] = key

When you look at this algorithm’s parameters, you might wonder why we

have chosen to pass in the root location. Because this routine is not recursive,

the root of the heap should always be location 1. You will see, however, that

this additional parameter will make it possible for us to use this function to

construct the heap from the bottom up. We pass in the size of the heap, because

as the elements get moved from the heap to the list, the heap shrinks.

Constructing the Heap

The way that we have chosen to implement the FixHeap function means that

we can use this in the initial construction of the heap. Any two values can be

treated as leaves of a vacant node. We do not need to do any work on the sec-

ond half of the list because they are all leaves. We just need to construct small

heaps from the leaves and then combine these until eventually all values are in

the heap. This is accomplished by the following loop:

for i = N/2 down to 1 do

FixHeap( list, i, list[ i ], N )

end for