Assignment 05: Linear Priority Queue
Implementing a priority queue with a linear data structure
Overview
In this lab, you will implement a new ADT, the priority queue. Like a standard queue, stack, and deque, a priority queue allows a user to add and remove elements from a collection. Unlike a standard queue, a priority queue allows the user to specify a priority for each element when it is added. The removal method then returns and removes the element with the highest priority.
In this lab you will provide an implementation of a priority queue using a linear data structure of your choosing (e.g., linked list or array).
Background
Priority Queues
A priority queue is a container of elements where each element has an associated priority. (You may assume that priorities of elements are distinct, so that given any pair of elements, one has strictly higher priority than the other.) More formally, the state of a priority queue can be represented as a set of pairs:
\[S = \{(k_0, x_0), (k_1, x_1), \ldots, (k_{n1}, x_{n1})\}\]where each \(x_i\) is an element in the queue and \(k_i\) is an integer representing \(x_i\)’s priority. We assume that smaller numbers indicated higher priority: an elment with priority \(1\) has higher priority than an element with priority \(2\), and so on. In the state \(S\) depicted above, we assume \(k_0 < k_1 < \cdots < k_{n1}\) so that \(x_0\) has the highest priority, etc.
In addition to the usual \(\mathrm{size}()\) and \(\mathrm{isEmpty}()\) methods, priority queues offer the following methods:

\(\mathrm{min}()\) returns the element with highest priority in the queue. For the state \(S\) as above, the element \(x_0\) is returend.

\(\mathrm{insert}(k, x)\) insert element \(x\) into the queue with priority \(k\). If \(k\) satisfies \(k_i < k < k_{i+1}\), then after this operation, the state is updated to
\[S = \{(k_0, x_0),\ldots, (k_i, x_i), (k, x), (k_{i+1}, x_{i+1}),\ldots, (k_{n1}, x_{n1}).\}\] 
\(\mathrm{removeMin}()\) remove and return the element with highest priority in the queue. This operation updates the state to
\[S = \{(k_1, x_1), \ldots, (k_{n1}, x_{n1})\}\]and returns the value \(x_0\).
See SimplePriorityQueue.java
for a specification of a Java interface for the priority queue ADT.
Your Task
For this assignment, you will implement a priority queue called LinearPriorityQueue
. You may choose any linear data structure (linked list, array, or some variant thereof) to store the contents of your priority queue. However, the running times of the operations for your priority queue must be as follows for a priority queue storing \(n\) elements:
 The
removeMin()
andmin()
methods must run in time \(O(1)\).  The
insert(k, x)
method must run in time \(O(n)\).
You can test the correctness of your implementation using the PriorityQueueTester.java
provided. Additionally, you will test the performance of your LinearPriorityQueue
to empirically verify that the running times of the operations are as specified above.
Code
Complete code: hw05.zip

SimplePriorityQueue.java
specifies a priority queue interface. 
PriorityQueueTester.java
tests your priority queue (hence heap) implementation for correctness. 
RunTimer.java
andCSVWriter.java
, the usual tools for testing running times.
Questions

Write a program,
PriorityQueuePerformanceTester.java
, that tests the empirical running times of yourinsert
andremoveMin
methods over a wide range of priority queue sizes. You should insert elements with random priorities, but the particular values are unimportant. Plot the running times against instance size. Do the empirical running times match your expectations for the theoretical running time? 
Approximately how many elements can you
insert
with random priorities in 1 second? How long does it take to remove these elements with theremoveMin
method? 
What data structure did you use to represent your priority queue, and why?

While the worst case running time of your
insert
method should be \(O(n)\), are there executions in which the running time will be significantly faster than this? E.g., are there executions in which the calls toinsert
will take only \(O(1)\) (amortized) time?
What to Submit
LinearPriorityQueue.java
containing your priority queue implementation using a linear data structurePriorityQueuePerformanceTester.java
that runs the performance tests used to answer the questions aboveresponse.pdf
containing your responses to the questions above
Evaluation
Your submission will receive a score out of 10 points, broken down as follows:
 6 points for
LinearPriorityQueue.java
 code compiles, runs, and passes tests in
PriorityQueueTester.java
 code implements priority queue using a linear data structure (array or linked list)
 running times are as specified above
 code compiles, runs, and passes tests in
 4 points for responses to the questions above