Java Reference
In-Depth Information
PROGRAMMING PROJECTS
21.24
Write a program to compare the running time of using the
PriorityQueue
's
one-parameter constructor to initialize the heap with
N
items versus start-
ing with an empty
PriorityQueue
and performing
N
separate insertions.
Run your program for sorted, reverse sorted, and random inputs.
Suppose that you have a number of boxes, each of which can hold total
weight 1.0 and items
i
1
,
i
2
,
i
3
, ...,
i
N
,
which weigh
w
1
,
w
2
,
w
3
, ...,
w
N
,
respectively. The object is to pack all the items, using as few boxes as
possible, without placing more weight in any box than its capacity. For
instance, if the items have weights 0.4, 0.4, 0.6, and 0.6, you can solve the
problem with two boxes. This problem is difficult, and no efficient algo-
rithm is known. Several strategies give good, but not optimal, packings.
Write programs to implement efficiently the following approximation
strategies.
a.
21.25
Scan the items in the order given; place each new item in the
most-filled box that can accept it without overflowing. Use a pri-
ority queue to determine the box that an item goes in.
b.
Sort the items, placing the heaviest item first; then use the strat-
egy in part (a).
Implement both heapsort and quicksort and compare their performances
on both sorted inputs and random inputs. Use different types of data for
the tests.
21.26
Suppose that you have a hole at node
X.
The normal
percDown
routine is
to compare
X
's children and then move the child up to
X
if it is larger (in
the case of a max heap) than the element to be placed, thereby pushing
the hole down. Stop when placing the new element in the hole is safe.
Consider the following alternative strategy for
percDown
. Move elements
up and the hole down as far as possible without testing whether the new
cell can be inserted. These actions would place the new cell in a leaf and
probably violate heap order. To fix the heap order, percolate the new cell
up in the normal manner. The expectation is that the percolation up will
be only one or two levels on average. Write a routine to include this idea.
Compare the running time with that of a standard implementation of
heapsort.
21.27
Redo Exercise 8.20, using heapsort instead of mergesort.
21.28
Implement an external sort.
21.29
Search WWH ::
Custom Search