Assign5: PQ Sorted Array

The Priority Queue data structure

A standard queue processes elements in the first-in, first-out ("FIFO") manner typical of ordinary waiting lines. New elements are added to the back of the queue and the next element to be processed is taken from the front. Queues can be handy, but a FIFO strategy isn't always what's needed.

A hospital emergency room, for example, needs to schedule patients according to priority. A patient with a more critical problem will pre-empt others that arrived earlier, allowing their problems to be addressed earlier. The data structure that we need in order to enable this behavior is a priority queue. The highest priority element in the queue is considered frontmost and will be dequeued first. As we will see later on in the assignment there are many practical applications for a priority queue, both inside and outside of computer science!

PQSortedArray Class

In order to provide this desired functionality, we turn to harness the power of classes in C++ and define our own ADT class called PQSortedArray. This class will be defined and used much in the same way that we have seen so far with collection classes like the Queue, Vector, and Set. The only difference is that this time around, instead of relying on the Stanford libraries to define the behavior of these class, we take the power into our own hands! The whole purpose of designing a class in this case is to hide the messy details (keeping the elements in sorted order, always removing the one with highest priority, etc.) inside the implementation and present a clean abstraction for use by the client.

Although our discussion in class centered around how to use a binary heap as the data storage backing for a Priority Queue, we are first going to take a step back and try out a simpler approach to get you warmed up and thinking about class interfaces and dynamic memory. One possibility for implementing a priority queue would be to store the elements in an array and keep the array in sorted order. In this way, it is quick to find the frontmost element that should be dequeued, as it will always be either the first or the last element in the array, depending on whether we store the elements in increasing or decreasing order.

Below is the interface for the PQSortedArray class. Note that the public interface of the Priority Queue class is identical to that of the standard Queue. The only operational difference is that the highest priority element is treated as frontmost for peek/dequeue rather than the element that was enqueued first.

Ideally the class would be written as a generic that allows the user's choice of element type, but alas, we have yet to introduce you to those mechanisms, so we will have to settle for making the class specifically handle elements that are represented as integers. Importantly, the integer value will be treated as the element's priority. Smaller integers are higher priority than larger and will be dequeued first.

class PQSortedArray {
  public:
   
    PQSortedArray();
    ~PQSortedArray();
  
    void enqueue(int element);
    int dequeue();
    int peek() const;
    bool isEmpty() const;
    int size() const;
    void clear();

  private:
     int* _elements;
     int _count;
     int _capacity;
};

Note: For this part of the assignment, you will not be implementing the whole class interface, but rather just one component (function) of it) There is a lot of write-up in order to get you to the point of understanding what the task is, but worry not, you will only have to implement one function! We have provided a nearly complete implementation of the PQSortedArray class that is missing only the enqueue operation. Your goal is to review the given code to learn how the class operates and then implement the final missing operation.

The PQSortedArray stores the elements in an array. The array elements are to be stored in order of highest to lowest value. The enqueue operation must find the correct position in the array to place the new element and move the other elements aside to make room for it.

The other important job of enqueue is to grow the array when it is filled to capacity. As seen in the lecture example VectorInt, the task of enlarging the array fits nicely in a helper function. Add a declaration of the helper function to the private section of the class interface and define it as part of the class implementation. You can then call the helper from enqueue when appropriate.

Notes

Testing and timing

With a correct implementation of the missing enqueue function, you should now have a fully working priority queue. Use the provided tests to exercise the PQSortedArray. Work through any test failures and resolve the issues until you are confident your implementation is fully correct.

Once your code is finalized, do some time trials on the PQSortedArray operations. First predict what you expect to be the Big O of enqueue and dequeue. Use the SimpleTest timing operation to measure the execution time over 4 or more different size inputs. You should choose sizes so that the largest operation completes in under a minute or so.

Answer these questions in short_answer.txt: