C++ Data Structures and Algorithms

A Priority Queue is an Abstract Data Type that acts as a queue except that the order in which items are Dequeued is determined by their priority i.e., the item with the highest priority is Dequeued first. Accordingly, ItemType has a member variable, int priority, which is used by Compare To() to order items. (a) Suppose we modify the circular array version of QueueType to make it a priority queue. Enqueue works as usual: the new item is placed at the rear of the queue, regardless of priority. Dequeue works differently: First, the queue is searched for the item of highest priority, which is then returned by reference. Then, the dequeued item is replaced with the last item in the queue, and the rear index is updated accordingly. Implement this new version. (b) Suppose we change the implementation in part (a) to keep the circular array sorted at all times. Compare the performance of both approaches