In the first three parts of this lab, we will be creating our own implementation of the heap data structure as a Priority Queue in order to better understand their implementation and behavior.
As in Lab 5, our implementation will inherit from Java’s AbstractQueue<T> abstract class so that we can focus only on implementing the fundamental behavior of a Priority Queue and not all the extra methods needed to be a Java Collection<T>. Once again, we will be using generics so that our MyPriorityQueue collection stores items of type T. Ultimately, our implementation will be very similar to Java’s own PriorityQueue<T> class!
In Visual Studio Code, create a new file in your GitHub repository called MyPriorityQueue.java. Within this file, you should create a new class using the code:
public class MyPriorityQueue<T> extends AbstractQueue<T>
ReadMe
As you are implementing your solutions, do not forget to include documentation using Javadocs! This is important practice to get into the habit of, and it will be a portion of your solution grade for the remainder of the semester.
The class itself (at the top), each instance variable, and each method should have a short Javadoc comment.
Your MyPriorityQueue class should have two private instance variables:
heap: an ArrayList storing items of type T that we will use as the array representation of our heapcomparator: the Comparator<T> used by the Priority Queue and heap to compare two items of type T to follow the min heap-order property of the heap.Both of the instance variables should be private so that their access (especially assigning values) can be controlled through the MyPriorityQueue class.
The MyPriorityQueue class should have only one constructor: a public constructor that takes as a parameter the Comparator<T> to use for comparing items of type T, which it should save as the comparator instance variable. It should also create the ArrayList<T> heap used to store the heap.
ReadMe
In our class lectures, we described the first item of the heap as being the number -∞. That will not quite work in our implementation since type T might not be a number (e.g., it will be the Task class in our application in Part 4 of the lab. Instead, we will store null in the 0 index of heap and use it similar to -∞.
Since we made our instance variables private, we can add “getter” methods in order to still be able to retrieve values from outside of the class. You should add one such methods:
public Comparator<T> getComparator(), which returns the value of the comparator instance variableInstead of creating a getter method for the second heap instance variable, we will instead implement the public Iterator<T> iterator() method required by the AbstractQueue<T> abstract class, which will allow us to iterate through the items in the heap.
Hint
This method should simply return the Iterator<T> of the heap instance variable:
return this.heap.iterator();
We will be able to use this Iterator<T> to help us debug our heap data structure!
Next, we should implement two additional methods needed by Collection<T> in Java:
public int size(), which returns the number of items stored in the Priority Queue and its heapHint
Since we are storing null in the 0 index of the heap instance variable, we can find the size of the Priority Queue as being one less than the size of the heap instance variable.
public void clear(), which removes all items from the Priority Queue.Hint
We can again use the clear() of the heap ArrayList, but do not forget to re-add the null value into the 0 index of the heap instance variable.
Ultimately, we will create unit tests to test each of the methods implemented in our class. However, we cannot do so until we implement the ability to enqueue items, which we will do in the next part of the lab.
Don’t forget to frequently save your progress to GitHub using the add/commit/push commands with git.