Advanced Data Structures - Java Concepts - page 1040

΢ Exercise P16.21. Time the results of heapsort and merge sort. Which
algorithm behaves better in practice?

Additional programming exercises are available in WileyPLUS.

PROGRAMMING PROJECTS

΢΢΢Project 16.1. Implement a BinaryTreeSet class that uses a
TreeSet to store its elements. You will need to implement an iterator
that iterates through the nodes in sorted order. This iterator is somewhat
complex, because sometimes you need to backtrack. You can either add
a reference to the parent node in each Node object, or have your iterator
object store a stack of the visited nodes.

΢΢΢Project 16.2. Implement an expression evaluator that uses a parser to
build an expression tree, such as in Section 16.6 . (Note that the resulting
tree is a binary tree but not a binary search tree.) Then use postorder
traversal to evaluate the expression, using a stack for the intermediate
results.

΢΢΢Project 16.3. Program an animation of the heapsort algorithm,
displaying the tree graphically and stopping after each call to fixHeap .

762
763

ANSWERS TO SELF-CHECK QUESTIONS

1. Efficient set implementations can quickly test whether a given element is a
member of the set.

2. Sets do not have an ordering, so it doesn't make sense to add an element at
a particular iterator position, or to traverse a set backwards.

3. A set stores elements. A map stores associations between keys and values.

4. The ordering does not matter, and you cannot have duplicates.

5. Yes, the hash set will work correctly. All elements will be inserted into a
single bucket.