Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
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_inline69071.

   program39592
Program: HeapSorter class buildHeap method.

Why does buildHeap start percolating at tex2html_wrap_inline57766? A complete binary tree with n nodes has exactly tex2html_wrap_inline67461 leaves. Therefore, the last node in the array which has a child is in position tex2html_wrap_inline57766. 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.

   figure39606
Figure: Building a heap.




next up previous contents index

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