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(item, priority)
Add the given item to the queue, with the given priority. (Sometimes called push.)
head()
Return the highest priority item in the queue. (This is sometimes called peek or top.)
remove()
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.
While you are working, you must use Git version control to maintain control of your development process.
Task 2 Testing
Test all five PriorityQueue implementation classes thoroughly using JUnit.
Task 3 Reflective report
Write a report of about 800 words covering the following:
1. The advantages and disadvantages of each of the different implementations. One thought that might help you here is to consider how they each would perform if the queue had an extremely large number of items in it. Think about how long it would take to add or remove an item if the queue had a thousand items in it? A million? A billion?
2. The testing methodology you chose to adopt, and why you believe that your code is correct.
3. Applications of priority queues in "real life" contexts. (You will obviously need to do some research in order to answer this part well.)
4. An analysis of your own development process, including an analysis of the time taken; a description and analysis of the defects you introduced into your code, how long they remained in there, and how you discovered and corrected them; and an analysis of the effectiveness of your chosen way of working with version control. In order to do a good job here, you will need to keep records as you work. I will make sample data recording forms available to you.