Priority Queue in Data Structure Assignment

Assignment Task

Index Priority Queue

In this assignment, we will extend the implementation of a minimum binary heap from tutorial week 8 to build a data structure called a (minimum) index priority queue. In an index priority queue, the elements we store consist of two parts, a priority and an index. Think of the situation of a patient coming into the emergency room. The priority measures the severity of the patient's condition. We see patients in order of priority. The index is like the patient's name. This gives a way to refer and call up patients: "Patient Bob, the doctor is ready to see you no.

Likewise, associating each element with an index, or "name", will allow us to call up an element in the queue by its index: we can remove an element with a given index, change the priority associated with an index, or tell if the queue contains an element with a given index. None of these things can be done in an ordinary priority queue.

To keep things simple we will always assume that the indices are 0, ..., N-1, where N is the maximum possible number of elements. The maximum number of elements will be specified by the user when the index priority queue is initialized.

The class is called IndexPriorityQueue. It is a templated class where T will denote the type of the priorities. Comparison of priorities is what determines the ordering of the elements in the queue. You should think that T could be a very large type, where it is expensive to make copies or assignments---we want to avoid this as much as possible. Let's go over the member functions you have to implement.

Constructor

The constructor takes as a parameter an integer N which is the maximum number of elements the priority queue can hold. Each element is a priority with an associated index. The indices will be 0, N - 1 when the parameter to this constructor is N. 

Basic Operations

If an element with the parameter index is already in the priority queue, then do nothing. Otherwise, add a new element with priority priority and index index to the index priority queue. This is similar to the push in a normal priority queue except that now a priority is inserted with its associated index. This function should work in time ????(log⁡????)O(logN).

Respectively return whether or not there are any elements in the index priority queue and the number of elements in the index priority queue. These functions should work in constant time.

Testing

We provide 20 tests in the main cpp to get you started. You are free to modify the main. cpp as you like. When you hit "mark" your code will be checked against the 20 tests in main plus an additional 20 hidden tests.

Functionality: This is graded purely on the basis of passing test cases. When you hit mark your code will be run on 40 test cases. Your functionality score is 0.3 times the number of test cases you pass.

This IT and Computer Science has been solved by our PHD Experts at My Uni Papers.