Topic: Priority Queue assignment

In this assignment, you implement a min-heap, use the heap to implement a priority queue, and finally use the priority queue to schedule real-time processes.

You must also design a class Record and a class satisfying the Comparator interface, based on the description below.

For your heap and priority queue, you may take inspiration from the book (chapter 6.6), but your heap will differ from the one in the book. You should implement your min-heap as a class supporting the two methods add (as defined in the interface Collection) and remove (as defined in the interface Queue).

The constructor for both your heap and priority queue classes should take two arguments: an initial capacity, and a Comparator. This is similar to one of the constructors for the standard Priority Queue class.

Your heap add method should use a loop to re-heapify from the bottom up. This is what the code in the textbook does, and you may take inspiration from the book. If the array is full, your code should allocate a larger array and copy the existing heap into the new array, then use the larger array for the heap storage.

Your heap remove method should use a recursive method to re-heapify. This is different from the way the book does it.

Every time you add or remove an element, your heap code must print:

the number of levels in the tree traversed to re-heapify the tree, as well as

the time taken for the entire operation.

To record the time taken, your code should call System.nanoTime at the beginning of each of the two methods and save the value as the start time. It should then call System.nanoTime again at the end, and print the difference between the two times.

The difference may be zero if your system clock does not update the time quickly enough, but otherwise should accurately report how many nanoseconds (billionths of a second) it took to execute your code.

Your priority queue class uses the heap class to provide the priority queue operations add and poll defined in the standard Java class PriorityQueue for Java Java Programming..