|
|
// HeapSort.java version 1.3
package nzdis.util;
// If you are using JDK 1.2 include the following import:
import java.util.Comparator;
/*
Source for Williams and Floyd's TopDown HeapSort
Copyright 1996-1998
Roedy Green
Canadian Mind Products
5317 Barker Avenue
Burnaby, BC Canada V5H 2N6
tel: (604) 435-3052
mailto:roedy@mindprod.com
http://mindprod.com
May be freely distributed for any purpose but military.
Version 1.1 adds new address and phone number.
Version 1.2 puts HeapSort into a package.
Version 1.3 is compatible with the JDK1.2 Comparator/Comparable interface.
1998 Dec 28
This simple heapsort demonstrates the use of a delegate
object to implement a callback. A heapsort works much
like a cutthroat bureaucracy with underlings constantly
challenging their bosses for dominance.
This sort works particularly well if data are already
sorted or are already nearly sorted. Unfortunately it is
"unstable" meaning it may disturb the existing order of
items with equal keys.
I have offered this sort to the US military. They offered
to attempt to prove it is bug-free. This is the algorithm
Abundance uses internally for keeping arrays sorted.
The algorithm may prove especially useful if you want to
maintain an array sorted in several different orders and
add or delete elements usually only a few at a time.
An improved version of this sort would build the heap from
the bottom up for a little extra speed and would avoid the
need for a separate workspace array. It would do all its
work with the user's array.
RadixSort is faster than HeapSort which in turn is faster
than QuickSort.
*/
// HeapSort to sort user's array of objects.
// Based on Williams' non-recursive top down heap sort.
// This sort works well if the items are already partially or
// completely sorted.
// Unfortunately the sort is not "stable", namely it may disturb
// the existing order of equal keys.
// We use an analogy of bosses and peons in a highly competitive
// corporate hierachy to describe the sort algorithm.
// The algorithm will be of more interest with parallel processing.
public class HeapSort {
private static final String EmbeddedCopyright =
"Copyright 1996-1998 Roedy Green, Canadian Mind Products, http://mindprod.com";
private static final boolean debugging = false;
// callback object we are passed that has
// a compare(Object a, Object b) method.
private Comparator delegate;
// create a HeapSort object and sort the user's array
public static void sort (Object [] userArray, Comparator delegate ) {
HeapSort h = new HeapSort();
h.userArray = userArray;
h.delegate = delegate;
if ( h.isAlreadySorted() ) return;
h.offices = new Object [userArray.length]; // work area
h.lastIndex = -1;
h.assignOffices();
h.raidAllEmployeesBiggestFirst();
if ( debugging ) {
if ( ! h.isAlreadySorted() ) System.out.println("Sort failed");
}
} // end sort
// Sort work area.
// Arranged as a binary tree.
// Each boss has two underling peons.
// Peons of a boss are stored in 2i+1 and 2i+2.
// They are both equal to or smaller than him.
// The peons may be in either order.
// The superboss, who has the biggest key, lives in slot 0.
private Object [] offices;
// last used office index. Current number of employees-1;
private int lastIndex = -1;
// pointer to the array of user's objects we are sorting
private Object [] userArray;
// check if user's array is already sorted
private boolean isAlreadySorted() {
for ( int i=1; i<userArray.length; i++ ) {
if ( delegate.compare(userArray[i], userArray[i-1]) < 0 )
return false;
}
return true;
} // end isAlreadySorted
// Assign all the user's objects to an office.
// They are likely partially presorted, so we
// work from the end back, assigning the
// objects with likely biggest keys first
// to the lowest numbered office slots.
// We then allow each newcomer to challenge
// his bosses for dominance.
private void assignOffices () {
for ( int i = userArray.length-1; i>=0; i-- ) {
int juniorIndex = ++lastIndex;
offices[juniorIndex] = userArray[i];
challenge(juniorIndex);
} // end for
} // end assignOffices
// Remove the employees biggest first.
// Record this ordering in the userArray.
// Future versions may store it in
// offices[i] in the newly vacated slot
// and leave userArray undisturbed.
// Promote as necessary to fill the vacancy.
private void raidAllEmployeesBiggestFirst () {
for ( int i=offices.length-1; i>=0; i-- ) {
// raid the SuperBoss
userArray[i]= offices[0];
replaceVacancy(0);
}
} // end raidAllEmployeesBiggestFirst
// Promote challenger until he finds a boss
// with a bigger key than him or he becomes the superboss.
private void challenge(int challengerIndex) {
Object challenger = offices[challengerIndex];
while ( challengerIndex > 0 ) {
int bossIndex = (challengerIndex-1)/2;
Object boss = offices[bossIndex];
if ( delegate.compare(boss,challenger) < 0 ) {
// Boss is smaller than challenger
// demote the boss.
offices[challengerIndex] = boss;
// Let challenger have his office.
challengerIndex = bossIndex;
} else break;
// challenger has been promoted enough
} // end while
// install the challenger in his new office
offices[challengerIndex] = challenger;
} // end Challenge
// Promote as necessary to fill the vacancy
// and cascading vacancies.
// When we are done, the Office list is one shorter.
private void replaceVacancy (int vacantIndex) {
while ( vacantIndex < lastIndex ) {
int peonAIndex = vacantIndex * 2 + 1;
if ( peonAIndex > lastIndex ) { // There are no peons.
promoteJuniorToVacancy(vacantIndex);
break;
}
Object peonA = offices[peonAIndex];
int peonBIndex = peonAIndex +1;
if ( peonBIndex > lastIndex ) { // There is only one peon.
// Promote peonA.
offices[vacantIndex] = peonA;
// peonA's office is now vacant.
vacantIndex = peonAIndex;
promoteJuniorToVacancy(vacantIndex);
break;
}
// There are two peons.
Object peonB = offices[peonBIndex];
if ( delegate.compare (peonA, peonB) < 0 ) { // peonA is smaller.
// Promote peonB
offices[vacantIndex] = peonB;
// peonB's office is now vacant.
vacantIndex = peonBIndex;
} else { // peonA is bigger or equal to peonB.
// Promote peonA
offices[vacantIndex] = peonA;
// peonA's office is now vacant.
vacantIndex = peonAIndex;
}
} // end while
// the last office is now vacant.
lastIndex--;
} // end replaceVacancy
// There is a vacancy in the lowest echelon.
// Move the most junior person in to fill it.
// Then let him challenge his bosses.
private void promoteJuniorToVacancy (int vacantIndex) {
if ( vacantIndex < lastIndex ) {
offices[vacantIndex] = offices[lastIndex];
challenge(vacantIndex);
}
} // end promoteJuniorToVacancy
} // end HeapSort
|