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

Implementation

Program gif defines the class template HeapSorter<T>. The HeapSorter<T> class is derived from the abstract Sorter<T> base class. Three protected member functions are defined--BuildHeap, PercolateDown and DoSort. The DoSort routine comprises the body of the sorting algorithm. The BuildHeap and PercolateDown routines are used by DoSort to build the heap and then to sort the array.

   program39283
Program: HeapSorter<T> Class Definition

In the first phase of heapsort, the unsorted array is transformed into a max heap. Throughout the process we view the array as a complete binary tree. Since the data in the array is initially unsorted, the tree is not initially heap-ordered. We make the tree into a max heap from the bottom up. I.e., we start with the leaves and work towards the root. Figure gif illustrates this process.

   figure39297
Figure: Combining Heaps by Percolating Values

Figure gif (a) shows a complete tree that is not yet heap ordered--the root is smaller than both its children. However, the two subtrees of the root are heap ordered. Given that both of the subtrees of the root are already heap ordered, we can heapify the tree by percolating the value in the root down the tree.

To percolate a value down the tree, we swap it with its largest child. E.g., in Figure gif (b) we swap 3 and 7. Swapping with the largest child ensures that after the swap, the new root is greater than or equal to both its children.

Notice that after the swap the heap-order is satisfied at the root, but not in the left subtree of the root. We continue percolating the 3 down by swapping it with 6 as shown in Figure gif (c). In general, we percolate a value down either until it arrives in a position in which the heap order is satisfied or until it arrives in a leaf. As shown in Figure gif (d), the tree obtained when the percolation is finished is a max heap

The PercolateDown routine shown in Program gif implements the algorithm described above. The PercolateDown routine takes three arguments: a reference to the array; the number of elements in the array to be considered, n; and the position, i, of the node to be percolated.

   program40113
Program: HeapSorter<T> Class PercolateDown Member Function Definition

The purpose of the PercolateDown routine is to transform the subtree rooted at position i into a max heap. It is assumed that the left and right subtrees of the node at position i are already max heaps. Recall that the children of node i are found at positions 2i and 2i+1. PercolateDown percolates the value in position i down the tree by swapping elements until the value arrives in a leaf node or until both children of i contain smaller value.

A constant amount of work is done in each iteration. Therefore, the running time of the PercolateDown routine is determined by the number of iterations of its main loop (lines 5-15). In fact, the number of iterations required in the worst case is equal to the height in the tree of node i.

Since the root of the tree has the greatest height, the worst-case occurs for i=1. In Chapter gif it is shown that the height of a complete binary tree is tex2html_wrap_inline66396. Therefore the worst-case running time of the PercolateDown routine is tex2html_wrap_inline59891.

Recall that BuildHeap calls PercolateDown for tex2html_wrap_inline70351. If we assume that the worst-case occurs every time, the running time of BuildHeap is tex2html_wrap_inline59897.


next up previous contents index

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