Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
The BuildHeap routine shown in Program 
transforms an unsorted array into a max heap.
It does so by calling the PercolateDown routine
for 
.
Program: HeapSorter<T> Class BuildHeap Member Function Definition
Why does BuildHeap start percolating at 
?
A complete binary tree with n nodes
has exactly 
leaves.
Therefore, the last node in the array which has a child
is in position .
Consequently, the BuildHeap routine starts doing percolate down
operations from that point.
The BuildHeap visits the array elements in reverse order.
In effect the algorithm starts at the deepest node that has a child
and works toward the root of the tree.
Each array position visited is the root of a subtree.
As each such subtree is visited,
it is transformed into a max heap.
Figure illustrates how the BuildHeap routine
heapifies an array that is initially unsorted.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.
