Last updated 1998 January 11 by Roedy Green
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.
Alternatively, you could use a Compare interface instead of a Compare class.
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.
The source is also available to download.>
import java.util.Random; public class TestSort { // Test HeapSort by sorting 5000 random Strings public static void main (String[] args) { System.out.println("Start"); String [] anArray = new String [5000]; Random wheel = new Random(149); for (int i=0; i<anArray.length; i++){ anArray[i] = "A" + (wheel.nextInt()%52); } System.out.println("Start Sort"); long start = System.currentTimeMillis(); HeapSort.sort(anArray, new StringCompare()); long stop = System.currentTimeMillis(); System.out.println("Elapsed:" + (stop-start)); try { Thread.sleep(3000); } catch (InterruptedException e) {}; } // end main } // end class TestSort // Callback delegate to describe collating sequence // to HeapSort class StringCompare extends Compare { // Compare two Strings. Callback for sort. // effectively returns a-b; // e.g. +1 (or any +ve number) if a > b // 0 if a == b // -1 (or any -ve number) if a < b public final int compare ( Object a, Object b) { return ((String)a).compareTo((String)b); } // end compare } // end class StringCompare
// HeapSort to sort user's array of objects. // By Roedy Green roedy@mindprod.com 1996 June 5 // Based on Williams and Floyd's 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{ // callback object we are passed that has // a compare(Object a, Object b) method. private Compare delegate; // create a HeapSort object and sort the user's array public static void sort (Object [] userArray, Compare 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(); } // 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
// delegate object to hand to sort for callback compare public abstract class Compare { // compare effectively returns a-b; // e.g. +1 (or any +ve number) if a > b // 0 if a == b // -1 (or any -ve number) if a < b abstract int compare(Object a, Object b); // e.g. return ((String)a).compareTo((String)b); } // end class Compare
![]() |
![]() |
|
Canadian Mind Products | You can get an updated copy of this page from http://mindprod.com/heapsort.html |