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
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.