next up previous contents index Search
Next: 0.3.3.2 Analysis Up: 0.3.3 Heapsort Previous: 0.3.3 Heapsort

0.3.3.1 Building a Max-Heap

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.

Scott Gasch
1999-07-09