Java Reference
In-Depth Information
swap(array, 0, n - 1);
for
(
int
lastIndex = n - 2; lastIndex > 0; lastIndex--)
{
reheap(array, 0, lastIndex);
swap(array, 0, lastIndex);
}
// end for
}
// end heapSort
Like merge sort and quick sort, heap sort is an O(
n
log
n
) algorithm. As implemented here,
heap sort does not require a second array, but merge sort does. Recall from Chapter 9 that quick sort
is O(
n
log
n
) most of the time, but is O(
n
2
) in its worst case. Since we usually can avoid quick sort's
worst case by choosing appropriate pivots, it generally is the preferred sorting method.
Note:
The time efficiency of heap sort
Although heap sort is O(
n
log
n
) in the average case, quick sort usually is the sorting method
of choice.
Question 9
Trace the steps that the method
heapSort
takes when sorting the following array
into ascending order:96248753.
C
HAPTER
S
UMMARY
•
Since a heap is a complete binary tree, it has an efficient array-based implementation.
•
You add a new entry to a heap as the next leaf in a complete binary tree. You then make the entry float up to
its proper location within the heap.
•
You begin to remove the root entry of a heap by replacing it with the entry in the last leaf and then removing
the leaf. The result is a semiheap. You transform the semiheap into a heap by making the new root entry sink
down to its proper location within the heap.
•
You could create a heap from a given array of entries by adding each entry to the heap. A more efficient
approach considers the complete tree that the array represents and treats each nonleaf as a semiheap. You
transform each such semiheap into a heap by using the same technique that you use when removing the root
of the heap.
•
A heap sort uses a heap to sort the entries in a given array.
E
XERCISES
1.
Trace the formation of a maxheap by the constructor given in Segment 26.16 for each of the following arrays:
a.
10 20 30 40 50
b.
10 20 30 40 50 60 70 80 90 100
2.
Trace the addition of each of the following values to an initially empty maxheap:
10 20 30 40 50
Compare your trace with the results of Exercise 1a.