class Underflow
{
};
template <class Comparable>
class PriorityQueue
{
public:
bool isEmpty( ) const;
Comparable findMin( ) const;
void makeEmpty( );
void insert( const Comparable & x );
void removeMin( );
void removeMin( Comparable & minValue );
private:
vector<Comparable> items;
};
The basic algorithm is as follows. The items vector will store the items in the priority queue. The priority queue is empty if and only if items has size 0. To perform insert, do a push_back on items. To perform findMin, do a sequential search, returning the smallest item (if the priority queue is empty, throw an Underflow exception). To perform removeMin, find the location of the minimum item (you may want to add a private member function that can be shared by findMin and removeMin to help you avoid redundancy). Once the location is found, copy into this location the item in the last array position, and then resize the array, making it one smaller. The second form of removeMin uses an output parameter. Prior to overwriting the location that has the minimum, copy the minimum value into the minValue parameter. This allows the caller to know what was removed from the priority queue. minValue is not an input parameter. Both forms of removeMin throw an exception if the priority queue is empty. HINT: Do the test for emptiness in the private member function suggested above!
Your test program should be self explanatory. In other words, you cannot simply output a bunch of numbers. Instead, output some answers, and have you program also output what the correct answers would be if there are no bugs. It should then be easy to verify that the program is indeed producing correct answers.
If you try to access the minimum of an empty priority queue, your program will throw the exception and terminate (i.e. crash). You do not have to try to catch the exception. So your main program does not need to test this case, although you may want to test it separately to convince yourself that it works. (In other words, you can write a second version of main for yourself, try to remove from an empty priority queue and see if main crashes, as would be expected if you correctly threw the exception.)