Projects

1. Design and implement a sorting algorithm using one of the priority queue implementations described in this chapter.
2. Complete the BinaryHeap class declared in Program  by providing suitable definitions for the following member functions: CompareTo, IsFull, Accept and NewIterator. Write a test program and test your implementation.
3. Complete the LeftistHeap class declared in Program  by providing suitable definitions for the following member functions: LeftistHeap (two constructors), Left, Right and SwapContents. You must also have 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 declared in Program  by providing suitable definitions for the following member functions: BinomialTree (constructor), Count, Subtree 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 declared in Program  by providing suitable definitions for the following member functions: BinomialQueue (constructor), BinomialQueue (destructor), Purge, CompareTo, Accept and NewIterator. 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 concrete priority queue class using multiple inheritance to inherit the functionality from the BinaryTree class (Program ) and the interface from the PriorityQueue class (Program ).
7. Implement a concrete priority queue class using the binary search tree class from Chapter . Specifically, use multiple inheritance to inherit the functionality from the BST class (Program ) and the interface from the PriorityQueue class (Program ). You will require a complete implementation of the base class BST. (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. I.e., use the priority queue to group terms with the same exponent. Hint: See also Project .

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