|
The first step in a Heapsort algorithm is to build a max-heap! Any
array can be ``heap shaped'' if we look at it the right way; place the
root of the heap at element one (or zero) in the array. Further, let
any node's two children in the heap reside at indexes (2n) and (2n
+ 1) in the array. Our heap-shaped array, then, would look something
like this:
1
/ \
2 3
/\ /\
4 5 6 7
/ \
8 9
Note that each level of the heap is full. If we were to add an
element to this heap we would add at the end of the array, at position
ten. Position ten, by the above formula, is the left child of node
five.
However, in a max-heap every element has to have a greater key value
than either of its children. Clearly, then, the root node, or
position one in our array, must be the data item with the greatest key
value in the set to be sorted.
We can build this heap by putting our data items into the array in any
order and then ``heapifying'' the array. Examine the first non-leaf node in the heap-array and compare its key value against
that of its greatest child. If it is greater than its greater
children, proceed to the next non-leaf node and repeat this process.
However, if it is not greater than its greater children then swap
these elements. Before continuing to the next non-leaf node and
repeating the process the algorithm must be certain that the newly
demoted value is in the correct spot. Thus the process must recurse
on this demoted value before it can continue with the next leaf on its
way to the root. By moving up the whole heap-array in this manner all
nodes will end up being greater than their children.
| 
Search