Java Reference
In-Depth Information
Exercise R16.16. Could a priority queue be implemented efficiently as a
binary search tree? Give a detailed argument for your answer.
Exercise R16.17. Will preorder, inorder, or postorder traversal print a
heap in sorted order? Why or why not?
759
760
Exercise R16.18. Prove that a heap of height h contains at least 2
hɨ1
elements but less than 2
h
elements.
Exercise R16.19. Suppose the heap nodes are stored in an array, starting
with index 1. Prove that the child nodes of the heap node with index i
have index 2i and 2i+1, and the parent heap node of the node with
index i has index i/2.
Exercise R16.20. Simulate the heapsort algorithm manually to sort the
array
11 27 8 14 45 6 24 81 29 33
Show all steps.
Additional review exercises are available in WileyPLUS.
PROGRAMMING EXERCISES
Exercise P16.1. Write a program that reads text from
System.in
and
breaks it up into individual words. Insert the words into a tree set. At the
end of the input file, print all words, followed by the size of the resulting
set. This program determines how many unique words a text file has.
Exercise P16.2. Insert the 13 standard colors that the
Color
class
predefines (that is,
Color.PINK
,
Color.GREEN
, and so on) into a set.
Prompt the user to enter a color by specifying red, green, and blue integer
values between 0 and 255. Then tell the user whether the resulting color is
in the set.
Exercise P16.3. Add a
debug
method to the
HashSet
implementation
in
Section 16.3
that prints the nonempty buckets of the hash table. Run
