A heap sort primer
The heap sort algorithm is really composed of two parts...
- Build a heap from the array to be sorted.
- Sort the newly built heap.
A heap is simply a tree-like structure with nodes and
connections between them. A node may have 0, 1, or 2 child
nodes that connect from beneath, and exactly 1 parent
node connected above, unless the node is the topmost or root node. A heap
may be represented easily by an array if for every node at index
i, it's child nodes are located at indices
2i+1 and 2i+2 (assuming the array is zero indexed).
Then the value of the array at index i is the value for that node.
To have a valid heap, two properties must be met...
- The root node must have the highest value of the heap.
- All child nodes must have equal or less value than their parents.
Building the heap
The first stage involves converting an arbitrary array into a valid
heap. This is performed through the use of a utility function called
Sift(). What this function does is, given a node and a position in
the array, cause that node to "trickle" down from a high starting position
to its final appropriate position within the array. It's easy to see that
this procedure greatly eases the task of building and maintain a heap. All one
need do is call Sift() for every array element and the array becomes
a heap.
The Sift() procedure
The Sift() function performs two basic functions within a loop...
- Test to see if either child to the current node is larger.
- Swap the current node with the larger child.
The loop exits when either the node has reached the bottom of the
array (there are no more children beneath it) or no child of the node has
a greater value.
Sorting the heap
Once an array has been transformed into a heap, sorting the array actually
becomes trivial and requires only two simple steps...
- Swap the last node with the root, thereby placing the largest value
node at the bottom of the array.
- Use the Sift() function to move the new root node down to its
proper place.
These steps are repeated for smaller and smaller upper portions of the array
until the array is fully sorted. The visualization applet helps to demonstrate
how each of the two steps, building the heap, and sorting the heap, takes a
time on the order of O(nlogn). Consequently, since only two
stages are involved, the entire process also takes a time proportional to
O(nlogn) for an arbitrary array of n elements.
Developed by
Mike Copley, UH for ICS 665 (Prof. J. Stelovsky)