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.