Projects

1. Design and implement a sorting algorithm using one of the priority queue implementations described in this chapter.
2. Complete the BinaryHeap class introduced in Program  by providing suitable definitions for the following methods: compareTo, isFull, accept, and getEnumeration. Write a test program and test your implementation.
3.   Complete the LeftistHeap class introduced in Program  by providing suitable definitions for the following methods: LeftistHeap (constructor), getLeftHeap, getRightHeap, swapContents, and swapSubtrees. You will require a complete implementation of the base class BinaryTree. (See Project ). Write a test program and test your implementation.
4.   Complete the implementation of the BinomialTree class introduced in Program  by providing suitable definitions for the following methods: BinomialTree (constructor), getCount, and swapContents. You must also have a complete implementation of the base class GeneralTree. (See Project ). Write a test program and test your implementation.
5. Complete the implementation of the BinomialQueue class introduced in Program  by providing suitable definitions for the following methods: BinomialQueue (constructor), purge, compareTo, accept, and getEnumeration. You must also have a complete implementation of the BinomialTree class. (See Project ). Write a test program and test your implementation.
6. The binary heap described in this chapter uses an array as the underlying foundational data structure. Alternatively we may base an implementation on the BinaryTree class described in Chapter . Implement a priority queue class that extends the BinaryTree class (Program ) and implements the PriorityQueue interface (Program ).
7. Implement a priority queue class using the binary search tree class from Chapter . Specifically, extend the BinarySearchTree class (Program ) and implement the PriorityQueue interface (Program ). You will require a complete implementation of the base class BinarySearchTree. (See Project ). Write a test program and test your implementation.
8. Devise and implement an algorithm to multiply two polynomials:

   

   Generate the terms of the result in order by putting intermediate product terms into a priority queue. That is, use the priority queue to group terms with the same exponent. Hint: See also Project .

Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.