Heapsorts use the concept of a heap. A heap is a binary tree with the property that all records stored in nodes are in sorted order along the path from each node back to the root. The tree of Figure 8.7 is not a heap. Its records are not in sorted order along the path from each node to the root. For example, the path from node 10 (where 123 is stored) to the root is not in sorted order. That path has records 123, 10, 32 and 100. (The nodes in this chapter are numbered like the nodes on trees in Chapter 7 and are referred to by their number.) Notice that the tree has the same information as the data array, but the information has been spread out along different paths.
Figure 8.8(a) is a heap storing the same information. It is one of many heaps that can be created to store the information. Since the path from every node to the root is in sorted order, the record at the root of a heap must be as great as any other in the tree. The same holds for all subtrees. The record at the root of any subtree must be at least as great as any other record in the subtree. The root record may then be taken as the first record in a sorted output of the information stored in the tree.
To sort, output 536 first, and then remove it from the tree. Now suppose that somehow the records can be rearranged in the tree to create a new heap?/FONT>a process called reheaping. The result might look like Figure 8.8(b). This tree has one less node than the original. Clearly, this process of removing the root can be repeated, outputting it next in the sorted output, and reheaping. When all the records have been output in sorted order, the remaining tree will be the null binary tree (the heap will be empty), and a sort will have been obtained. The algorithm is stated simply:
To perform a heapsort:
1. Create a heap.
2. While the heap is not empty
a. output the record at the root of the heap,
b. remove it from the heap, and
c. reheap.
As stated, the algorithm is not detailed enough. It does not specify how to create a heap (step 1) or how to reheap (step 2).