A Heap Implementation - Data Structures and Abstractions with Java - page 684

26.19

Adjusting reheap . We must revise the method reheap so that it is suitable for our sorting algorithm.
The original method in Segment 26.11 uses the data fields heap and lastIndex of the class MaxHeap .
Here, we make them parameters of the method. Thus, we change the method's header, as follows:

private static <T extends Comparable<? super T>>
void reheap(T[] heap, int rootIndex, int lastIndex)
The portion of the array heap that represents the heap ranges from the index 0 to the index lastIndex .
The semiheap is rooted at the index rootIndex .
Since the heap begins at index 0 instead of 1, as it did in Segment 26.11, the left child of the
node at index i is at index 2 i + 1 instead of 2 i . Recall that Question 1 asked you to find this index.
This change affects the two statements within reheap that determine leftChildIndex .
The revised reheap appears as follows:

private static <T extends Comparable<? super T>>
void reheap(T[] heap, int rootIndex, int lastIndex)

{

boolean done = false ;
T orphan = heap[rootIndex];

int leftChildIndex = 2 * rootIndex + 1;

while (!done && (leftChildIndex <= lastIndex))
{

int largerChildIndex = leftChildIndex;
int rightChildIndex = leftChildIndex + 1;
if ( (rightChildIndex <= lastIndex) &&
heap[rightChildIndex].compareTo(heap[largerChildIndex]) > 0)

{

largerChildIndex = rightChildIndex;
} // end if
if (orphan.compareTo(heap[largerChildIndex]) < 0)
{

heap[rootIndex] = heap[largerChildIndex];
rootIndex = largerChildIndex;

leftChildIndex = 2 * rootIndex + 1;

}
else
done = true ;
} // end while
heap[rootIndex] = orphan;
} // end reheap

26.20

The method heapSort . The implementation of heap sort begins by calling reheap repeatedly, as
we did in the constructor given in Segment 26.16, to create an initial heap from the given array.
However, since the heap begins at index 0 instead of 1, we must adjust the loop somewhat:

for ( int rootIndex = n / 2 - 1; rootIndex >= 0; rootIndex--)
reheap(heap, rootIndex, n - 1);
This loop assumes n entries in the array heap , beginning at index 0. Exercise 3 at the end of this
chapter asks you to verify the starting value of rootIndex .
The complete method appears as follows:

public static <T extends Comparable<? super T>>
void heapSort(T[] array, int n)

{

// create first heap
for ( int rootIndex = n / 2 - 1; rootIndex >= 0; rootIndex--)
reheap(array, rootIndex, n - 1);