Your task is to develop, test and document a Java class library containing several alternative implementations of the PriorityQueue abstract data type.
A priority queue is like an ordinary queue, except that each item has a numerical priority and instead of being “first in, first out”, it is “highest priority, first out”. That is, each remove() operation takes out the item in the queue that has the highest priority.
The operations on the PriorityQueue abstract data type are:
Add the given item to the queue, with the given priority. (Sometimes called push.)
Return the highest priority item in the queue. (This is sometimes called peek or top.)
Remove the highest priority item from the queue. (Sometimes called pop.) isEmpty()
Return True if the queue is empty, otherwise False. There are several ways to implement this abstract data type:
1. Using an ordered (i.e. sorted) array.
Use a private array of items, which are stored in increasing order of priority. This means that the “head” of the queue (i.e. the next item to be removed) is always the last item in the array. The head() and remove() operations are simple, but the add() operation requires you to search along the existing items to find the correct place to insert the new item.
2. Using an unordered array.
Similar to #1, except that the items are inserted in order of arrival. This makes the add() operation easy, but in order to find or remove the highest priority item, you now have to scan through the entire list. When removing an item, you then have to shift down all the items after the one you’re removing so as to fill the gap.
3. Using an ordered linked list.
The array implementations have a problem in that the size of the array is fixed. A linked list does not have this limitation. Here the items are stored in descending order so that the highest priority item can be accessed directly. Insertion requires searching along the list for the correct insertion point. This is tricky with a linked list because you need to find the item before the insertion point so you can alter the value of its “next” pointer.
4. Using an unordered linked list.
This is a cross between #2 and #3, using a linked list, but inserting each new item at the head of the list. To find or remove the highest priority item, you have to scan along the entire list. When removing, you need to change the “next” pointer from the item before.
5. Using a heap.
A heap is a binary tree with two properties. First, it is complete, meaning that the places in the tree are filled in breadth-first order, i.e. left-to-right across each row in turn. Secondly, it has the heap property, meaning that each node has higher priority than both its children. This is implemented using an array. If an item is stored in the array at position n then its left child will be at position 2n+1 and its right child at 2n+2. With this system, the array is filled in increasing order and you then need to swap elements with their parents or children in order to maintain the heap property. The highest priority item is always in the first position in the array, i.e. at index 0. You will need to look up the details of how to implement a heap. (There are many different variations. The version required here is called a binary max heap.)
I have made starting code available on GitHub at https://github.com/mo04gw/PriorityQueue. This includes a PriorityQueue interface and a working version of implementation #1 (using a sorted array). It also has a simple, driver program called QueueManager that uses a PriorityQueue to manage a queue of people. As you will see from the code, this is set up so that the user can choose what implementation to use. As you add new implementation classes, you will need to add new code to QueueManager allowing the user to select the new implementations.
Task 1 — Coding
Complete the remaining four implementations of the PriorityQueue abstract data type (classes UnsortedArrayPriorityQueue, UnsortedLinkedPriorityQueue, SortedLinkedPriorityQueue and HeapPriorityQueue).
You do not have to “reinvent the wheel” here. The entire assignment is open book, so you are encouraged to search for relevant information online or in books. Remember to reference all your sources.
You are not allowed to use classes in the Java Collections Framework (e.g. class PriorityQueue, which implements a very similar abstract interface using an internal heap), but you are free to read and adapt any code you find, as long as you reference it correctly. (The standard library class would not work as a drop-in solution anyway, as they have made different design choices about how to handle the priority and generics.)
You are not allowed to modify the PriorityQueue interface supplied to you. You must implement it as is, unchanged. You must also use the given class names for the implementations.
Task 2 — Testing
Test all five PriorityQueue implementation classes thoroughly using JUnit.
It probably makes sense to write some of your JUnit tests as you work. Black box tests apply to all the implementations, since they should all give the same results. You may want to add extra white box tests that address particular “interesting” parts of the code for the different implementations.
I will show you how to set this up when we cover testing in class. Remember to document your tests so you can write about them in your report.