3.5 HEAPSORT 77
a. If the key is a number in the range of 0 to 2^64 , choose two options (one
smaller and one larger) for the number of bits that will be used on each
pass and indicate how many buckets and passes will be needed.
b. If the key is a string of 40 characters, choose two options (one smaller
and one larger) for the number of bits that will be used on each pass and
indicate how many buckets and passes will be needed.
c. Based on your answers to parts (a) and (b), can you give any general rec-
ommendations for how to make the choice of passes and key subdivi-
sions?
3.5 Heapsort
Heapsort is based on a special type of binary tree called a heap where for every
subtree the value at the root is larger than all the values in the two children.
There is no ordering relationship between the two children, so sometimes the
left child may be larger, and other times the right will be larger. A heap is con-
structed to be a complete tree where each level of the tree is filled before a new
level is started, and all node positions on a level are filled in order from left to
right.
The general idea of heapsort is to first construct a heap. The largest element
will then be at the root of the tree, because all smaller elements must be in the
children for this to be a heap. The root is then copied into the last location of
the list, and the heap is reconstructed without this largest element. The second
largest element will then be at the root, so we can remove it and reconstruct
the heap. This process is repeated until all of the elements have been moved
back to the list.
The general algorithm for this is
construct the heap
for i = 1 to N do
copy the root to the list
fix the heap
end for
There are a number of details that remain for this algorithm to be complete.
We must first determine what is involved in the process of constructing and
fixing the heap, because it will play a role in the efficiency of this algorithm.
We need to be concerned about how this algorithm will be implemented.
The overhead of actually creating a binary tree would be a problem as the size
