Today in class we defined a priority queue, which is a queue in which each element has a priority.  Elements are dequeued according to their priority (we'll say largest first, ties broken randomly).  The best way (from what we thus far know) to implement a priority queue is with a tree.  The only tricky part is when you dequeue an element which itself had children (left children, which are less than that element).  These must be connected to the parent of the dequeued element (or, if the dequeued element was the root, then the left children must become the new root).

Your assignment is to create a PriorityQueue class with the following declaration (given here in part -- you may add to this as necessary):

class PriorityQueue
{
  public:
    bool isEmpty( );   // return true if empty else false
    int  length( );    // return number of elements in queue

    void enqueue( const apstring item, int priority );
    void dequeue( apstring & item );
    void makeEmpty( );
}

1.  Enqueue.  This will be a line with just a letter e followed by a one-word string-value followed by an integer priority.  For this, your program should enqueue the value with the given priority and produce no output.

2.  Dequeue.  This will be a line just a letter d.  For this, your program should dequeue an element from the Priority Queue.  The output should be the value dequeued followed by a newline.  Note that the queue might be empty, in which case the output should be <empty>.

3.  Quit.  This will be a line with just a letter q.  For this, your program should print out a line which says <bye> and then (oddly enough) quit.

In preparation for semi-automatic grading, please be sure not to include any extraneous input or output.  No prompts, no cute output, just the bare minimum.  So, for example, on the following input:

e steelers 20
e browns 10
e bears 15
d
e dolphins 25
d
e dolphins 5
d
d
d
d
q

steelers
dolphins
bears
browns
dolphins
<empty>
<bye>

DK