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_{n-1}, x_{n-1})\}\]

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_{n-1}\) 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_{n-1}, x_{n-1}).\}\]

  • \(\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_{n-1}, x_{n-1})\}\]

    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:

  1. The removeMin() and min() methods must run in time \(O(1)\).
  2. 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

Questions

  1. Write a program, PriorityQueuePerformanceTester.java, that tests the empirical running times of your insert and removeMin 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?

  2. Approximately how many elements can you insert with random priorities in 1 second? How long does it take to remove these elements with the removeMin method?

  3. What data structure did you use to represent your priority queue, and why?

  4. 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 to insert will take only \(O(1)\) (amortized) time?

What to Submit

  • LinearPriorityQueue.java containing your priority queue implementation using a linear data structure
  • PriorityQueuePerformanceTester.java that runs the performance tests used to answer the questions above
  • response.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
  • 4 points for responses to the questions above