Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Building the Heap

The BuildHeap routine shown in Program gif transforms an unsorted array into a max heap. It does so by calling the PercolateDown routine for tex2html_wrap_inline70355.

   program40134
Program: HeapSorter<T> Class BuildHeap Member Function Definition

Why does BuildHeap start percolating at tex2html_wrap_inline58823? A complete binary tree with n nodes has exactly tex2html_wrap_inline68743 leaves. Therefore, the last node in the array which has a child is in position tex2html_wrap_inline58823. 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 gif illustrates how the BuildHeap routine heapifies an array that is initially unsorted.

   figure40148
Figure: Building A Heap




next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.