Assignment 3

CS 146
due April 5, 2001
100 points, plus 15 points extra credit

Reimplement the Apportioner class of Assignment 2 in each of the following ways:
  1. so that it uses a binary heap, where reprioritization is performed by deletion followed by reinsertion, and
  2. so that it uses a binary heap, where reprioritization is performed by percolating down the node to be reprioritized.
In each case, you should maintain a count of the number of element comparisons. This counter should be printable to a designated output stream by a method
void printComps(ostream& os)
and resettable by a method
void clearComps()

Test your implementations by linking to the file a3.cpp, obtainable from the class web site. Most of the code for heaps given in the textbook can be found in the interface and implementation files (heap.h and heap.cpp), also on the class web site. Note that some of these methods will have to be modified or overloaded to keep track of the number of element comparisons.

You should strongly consider the use of inheritance to facilitate code reuse.

For up to 15 points extra credit, you may parametrize your Apportioner class(es) by allowing the divisor method to vary. For full extra credit, you should be able to handle the harmonic mean function (which given n, returns the inverse of the arithmetic mean of 1/n and 1/(n+1)) and the geometric mean function (which given n, returns the square root of the product of n and n+1), in addition to the arithmetic mean function itself (which was used in Assignment 2).

If you complete the extra credit, you should use the test file a3xc.cpp rather than a3.cpp. Note that for the US data, the geometric and arithmetic means return the same apportionment, while the harmonic mean differs from these in exactly two pairs of states.