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

Building the Heap

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

   program39843
Program: HeapSorter class BuildHeap method.

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

   figure39857
Figure: Building a heap.




next up previous contents index

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