/****************************************************************************** Heapsort ---------------------------------------------------- Copyright (c) Gunnar Gotshalks. All Rights Reserved. Permission to use, copy, modify, and distribute this software and its documentation for NON-COMMERCIAL purposes and without fee is hereby granted. *******************************************************************************/ package FlexOr.searchAndSort; import FlexOr.container.*; import java.lang.reflect.*; /** Sort an array of objects using heapsort.
@author Gunnar Gotshalks
@version 1.0 1999 Jan 15
*/
public class Heapsort implements ArraySort {
/**
@param array Array of elements to be sorted.
@param bp Defines how array elements are compared.
*/
public void sort(final Object[] array, final BinaryPredicate bp) {
execute(array, bp);
}
/** The heap sort method.
@param array Array of elements to be sorted.
@param bp Defines how array elements are compared.
*/
public static void execute(final Object[] array, final BinaryPredicate bp) {
int length = Array.getLength(array);
heapify(array, length-1, bp);
// Loop invariant: array[i+1 .. length-1] is sorted.
// and array[0..i] is a heap
// and array[0] is the "biggest" with respect to to bp
for (int i = length-1 ; i > 0 ; i--) {
swap(array, 0, i);
restoreHeapDown(array, 0, i-1, bp);
}
}
/** Rearrange, if necessary, heap elements to restore the heap property
with respect to comparison
.
Requires: True Ensure: heap has the heap property. */ private static void heapify(final Object[] heap, final int last, final BinaryPredicate bp) { for (int i = last/2 ; i >= 0 ; i-- ) { restoreHeapDown(heap, i, last, bp); } } /** Percolate down the obj at the root of the current subtree, if it violates the heap property.Requires: Subtrees at 2*root and 2*root+1 have the heap property Ensures: Heap property holds in the subtree beginning at root. */ private static void restoreHeapDown(final Object[] heap, final int root, final int last, final BinaryPredicate bp) { int left = 2*root+1; if (left > last) return; int right = left + 1; if (right > last) { // Only a left child exists if (bp.execute(heap[left], heap[root])) return; else { swap(heap, root, left); return; } } // Both children exist. if (bp.execute(heap[left], heap[root])) { if (bp.execute(heap[right], heap[root])) return; else { swap(heap, root, right); restoreHeapDown(heap, right, last, bp); } } else { if (bp.execute(heap[right], heap[root])) { swap(heap, root, left); restoreHeapDown(heap, left, last, bp); } else { if (bp.execute(heap[right], heap[left])) { swap(heap, root, left); restoreHeapDown(heap, left, last, bp); } else { swap(heap, root, right); restoreHeapDown(heap, right, last, bp); } } } } /** Exchange elements heap[a] and heap[b]. */ private static void swap(Object[] heap, int a, int b) { Object tmp; tmp = heap[a]; heap[a] = heap[b]; heap[b] = tmp; } }