class HeapSorter
extends Sorter {
/**
Make sure the root of a heap obeys the heap property, pushing it down the
heap until it does so.
@param array The array containing the segment containing the heap.
@param left The index of the heap's leftmost element; this is the root.
@param right One past the index of the heap's rightmost element.
*/
private <T extends Comparable<T>> void
trickleDown(T array[], int left, int right) {
int root = 0;
while (true) {
int c = 2*root + 1;
final int cl = 2*(root + 1);
if (c + left >= right)
break;
if ( (cl + left < right)
&& (array[left + c].compareTo(array[left + cl]) < 0))
c = cl;
if (array[left + root].compareTo(array[left + c]) > -1)
break;
swap(array, left + root, left + c);
root = c;
}
}
/**
Turn an array segment into a heap: the value at every element in the
segment is no less than the values at the children elements.
@param array The array containing the segment to be heapified.
@param left The index of the leftmost element in the array segment to be
heapified.
@param right One past the index of the rightmost element in the array
segment to be heapified.
*/
private <T extends Comparable<T>> void
heapify(T array[], int left, int right) {
final int n = right - left;
for (int c = 1; c < n; c++)
while (0 < c) {
final int p = c/2;
if (array[left + p].compareTo(array[left + c]) > -1)
break;
swap(array, left + p, left + c);
c = p;
}
}
public String
name() { return "heapsort"; }
<T extends Comparable<T>> void
sort(T array[], int left, int right) {
// Permute the array segment array[left..right - 1] such that if left <= i
// < j < right, then array[i] < array[j].
heapify(array, left, right);
for (int i = right - left - 1; i > 0; i--) {
swap(array, left, left + i);
trickleDown(array, left, left + i);
}
}
}
This page last modified on 24 January 2006.