78 SORTING ALGORITHMS
of the list grows. We can, however, use the space for the list itself and do this
sort without extra space. We can “build” the list into a heap if we notice that in
a heap each internal node has two children, except for perhaps one node
toward the bottom. If we consider the following mapping, we can use the list
to hold these values. For the node at location i, we will store its two children at
locations 2 *i and 2 *i + 1. Notice that this process produces distinct locations
for each node’s children. We know that node i is a leaf if 2 *iis greater than N,
and we know that node i has only one child if 2 *i is equal to N. Figure 3.3
shows a heap and its list version.FixHeap
When we take the largest element out of the root and move it to the list, this
leaves the root vacant. We know that the larger of its two children needs to be
moved up, but then that child’s node becomes vacant, and so we look at its two
children, and so on. In this process, we need to maintain the heap as close to a
complete tree as possible. When we fix the heap, we will also pass in the right-
most node from the bottom level, to be inserted back into the heap. This will
remove nodes evenly from the bottom. If we don’t do this and all of the large
values are on one side of the heap, the heap will be unbalanced and the algo-
rithm’s efficiency will go down. This gives us the following algorithm:FixHeap( list, root, key, bound )
list the list/heap being sorted
root the index of the root of the heap
81161 2 7 3 45 91012Locations 123456789101112■FIGURE 3.3^121011598612734
A heap and its list
implementation