Java Reference
In-Depth Information
26.16
Another constructor. We can use the technique described in Segment 26.14 to implement another
constructor for the class MaxHeap . Suppose that n entries for our heap are given in an array of
exactly n locations. The following constructor takes this array, copies it into the data field heap , and
uses reheap to create a heap. Although the entries in the given array begin at index 0, we place
them into the array heap beginning at index 1.
public MaxHeap(T[] entries)
{
// the cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempHeap = (T[]) new Comparable[entries.length + 1];
heap = tempHeap;
lastIndex = entries.length;
// copy given array to data field
for ( int index = 0; index < entries.length; index++)
heap[index + 1] = entries[index];
// create heap
for ( int rootIndex = lastIndex / 2; rootIndex > 0; rootIndex--)
reheap(rootIndex);
} // end constructor
Heap Sort
26.17
We can use a heap to sort an array. If we place the array items into a maxheap and then remove them
one at a time, we will get the items in descending order. We saw in Segments 26.13 and 26.14 that
using reheap instead of add is a more efficient way to create a heap from an array of items. In fact,
we wrote a constructor in the previous segment that invoked reheap for this purpose. So if a is the
array of items—strings, for example—we could use this constructor to create the heap, as follows:
VideoNote
The heap sort
MaxHeapInterface<String> myHeap = new MaxHeap<String>(a);
As we remove the items from myHeap , we could place them in order back into the array a . The
problem with this approach is the additional memory required, since the heap uses an array besides the
given array. However, by mimicking the heap's array-based implementation, we can make this
approach more efficient without using the class MaxHeap . The resulting algorithm is called a heap sort .
26.18
To create an initial heap from the given array, we call reheap repeatedly, as we did in the construc-
tor given in Segment 26.16. Parts a and b of Figure 26-9 show an array and the heap that results
after this step. Since the array to be sorted begins at index 0, but in the constructor the heap begins
at index 1, we must adjust reheap , as you will see.
The largest item in the array of Figure 26-9b is now first in the array, so we swap it with the
last item in the array, as Figure 26-9c shows. The array is now partitioned into a tree region and a
sorted region.
Following this swap, we call reheap on the tree portion—transforming it into a heap—and
perform another swap, as Figures 26-9d and 26-9e illustrate. We repeat these operations until the
tree region consists of one item (Figure 26-9k). The array is now sorted into ascending order.
Notice that the array actually is sorted in Figure 26-9g, but the algorithm does not detect this fact.
 
 
Search WWH ::




Custom Search