Java Reference
In-Depth Information
of size n 1. Removing the new maximum (root) value places the second largest
value in position n2 of the array. After removing each of the remaining values in
turn, the array will be properly sorted from least to greatest. This is why Heapsort
uses a max-heap rather than a min-heap as might have been expected. Figure 7.15
illustrates Heapsort. The complete Java implementation is as follows:
static<EextendsComparable<?superE>>
voidheapsort(E[]A){
//Theheapconstructorinvokesthebuildheapmethod
MaxHeap<E>H=newMaxHeap<E>(A,A.length,A.length);
for(inti=0;i<A.length;i++)//Nowsort
H.removemax();//Removemaxplacesmaxatendofheap
}
Because building the heap takes (n) time (see Section 5.5), and because
n deletions of the maximum element each take (log n) time, we see that the en-
tire Heapsort operation takes (n log n) time in the worst, average, and best cases.
While typically slower than Quicksort by a constant factor, Heapsort has one spe-
cial advantage over the other sorts studied so far. Building the heap is relatively
cheap, requiring (n) time. Removing the maximum element from the heap re-
quires (log n) time. Thus, if we wish to find the k largest elements in an array,
we can do so in time (n + k log n). If k is small, this is a substantial improve-
ment over the time required to find the k largest elements using one of the other
sorting methods described earlier (many of which would require sorting all of the
array first). One situation where we are able to take advantage of this concept is
in the implementation of Kruskal's minimum-cost spanning tree (MST) algorithm
of Section 11.5.2. That algorithm requires that edges be visited in ascending order
(so, use a min-heap), but this process stops as soon as the MST is complete. Thus,
only a relatively small fraction of the edges need be sorted.
7.7
Binsort and Radix Sort
Imagine that for the past year, as you paid your various bills, you then simply piled
all the paperwork onto the top of a table somewhere. Now the year has ended and
its time to sort all of these papers by what the bill was for (phone, electricity, rent,
etc.) and date. A pretty natural approach is to make some space on the floor, and as
you go through the pile of papers, put the phone bills into one pile, the electric bills
into another pile, and so on. Once this initial assignment of bills to piles is done (in
one pass), you can sort each pile by date relatively quickly because they are each
fairly small. This is the basic idea behind a Binsort.
Section 3.9 presented the following code fragment to sort a permutation of the
numbers 0 through n 1:
for(i=0;i<n;i++)
B[A[i]]=A[i];
