Java Reference
In-Depth Information
3.
The method
heapSort
given in Segment 26.20 contains a loop that creates an initial heap from an array of
n
values. The loop variable
rootIndex
begins at
n/2
-
1
. Derive this starting value and show that the loop executes
the same number of times as the corresponding loop in the constructor given in Segment 26.16.
4.
Trace the steps of a heap sort on each of the following arrays:
a.
10 20 30 40 50 60
b.
60 50 40 30 20 10
c.
20 50 40 10 60 30
5.
Consider an array that represents a heap. Suppose that you replace the value at index
i
with a new value. It is
likely that you will no longer have a heap. Write an algorithm that will give you a heap again.
6.
Segment 26.15 showed that the complexity of creating a heap by using
reheap
is
§
·
h
-
¦
1
¨
2
l
-
1
¸
(
hl
-
+
1
)
⋅
O
¨
¸
©
l
=
1
¹
Show that this expression is equivalent to O(2
h
), which is O(
n
).
Hint
: First, change the summation variable from
l
to
j
, where
j
=
h
-
l
+
1. Then show by induction that
h
¦
h
2
h
2
2
j
=
32
⁄
-
------------
j
⁄
j
=
2
7.
Consider the loop in a heap sort that creates the initial heap from an array of
n
values (see Segment 26.20):
// create first heap
for
(
int
rootIndex = n / 2 - 1; rootIndex >= 0; rootIndex--)
reheap(array, rootIndex, n - 1);
Show that the actual number of calls to the method
compareTo
during the execution of this loop is no less than
n
-
1.
8.
Consider again the loop mentioned in the previous exercise. Show that the actual number of calls to the method
compareTo
during the execution of this loop is no greater than
n
log
2
n
.
9.
Heap sort is not the only way to sort an array using a heap. In this exercise you will explore a less efficient
algorithm. After building an initial heap, as you would in the first step of a heap sort, the largest value will be in
the first position of the array. If you leave this value in place and then build a new heap using the remaining
values, you will get the next largest value in the entire array. By continuing in this manner, you can sort the array
into descending order. If you use a minheap instead of a maxheap, you will sort the array into ascending order.
a.
Implement one of these sorts as the method
newSortUsingAHeap
.
b.
What is the Big Oh performance of this method?
P
ROJECTS
1.
Recall from Segment 23.31 of Chapter 23 that in a minheap, the object in each node is less than or equal to the
objects in the node's descendants. While a maxheap has the method
getMax
, a minheap has the method
getMin
instead. Use an array to implement a minheap.
2.
Compare the execution times of heap sort, merge sort, and quick sort on various arrays chosen at random. The
“Projects” section of Chapter 4 described one way to time the execution of code.
3.
Use a binary search tree in the implementation of
MaxHeapInterface
. Where in the tree will the largest entry
occur? How efficient is this implementation?
