Algorithms in a Nutshell

Heap Sort

We always need at least n−1 comparisons to find the largest element in an array A[0,n), but we want to minimize the number of elements that are compared directly to it. In sports, tournaments are used to find the "best" team from a field of n teams without forcing the ultimate winner to play all other n−1 teams. One of the most popular basketball events in the United States is the NCAA championship tournament, where essentially a set of 64 college teams compete for the championship title.^[11] The ultimate champion team plays five teams before reaching the final determining game, and so that team must win six games. It is no coincidence that 6=log (64). Heap Sort shows how to apply this behavior to sort a set of elements; its pseudocode description is shown in Figure 4-14.

Figure 4-14. Heap Sort fact sheet

A heap is a binary tree whose structure ensures two properties:

Shape property

A leaf node at depth k>0 can exist only if all 2^k−1 nodes at depth k−1 exist. Additionally, nodes at a partially filled level must be added "from left to right."

Heap property

Each node in the tree contains a value greater than or equal to either of its two children, if it has any.

The sample heap labeled (a) in Figure 4-15 satisfies these properties. The root of the binary tree must contain the largest element in the tree; however, note that the smallest element can be any of the leaf nodes. Although ...