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.

Finally, you must provide a driver class which creates a priority queue (after creating an appropriate comparator), reads a file (specified on the command line), and adds or removes things from the priority queue. The file has lines that have one of two forms:

schedule process deadline duration, or

run time.

where:

process is an arbitrary string,

deadline, duration, and time are longs representing time.

Some examples

Given the above example file, your program should print:

0: adding lunch with deadline 1300 and duration 30 0: adding work with deadline 7200 and duration 2300 0: adding homework with deadline 2359 and duration 300 0: busy with lunch with deadline 1300 and duration 30 30: done with lunch 30: busy with homework with deadline 2359 and duration 300 330: done with homework 330: busy with work with deadline 7200 and duration 2300 2400: adding work with deadline 7200 and duration 230 

For another example, suppose this was your schedule:

schedule work 60 30 schedule fun 40 30 run 50 run 100 

Your program should schedule fun before work (because in this case fun has an earlier deadline), and print the following:

0: adding work with deadline 60 and duration 30 0: adding fun with deadline 40 and duration 30 0: busy with fun with deadline 40 and duration 30 30: done with fun 30: busy with work with deadline 60 and duration 30 50: adding work with deadline 60 and duration 10 50: busy with work with deadline 60 and duration 10 60: done with work 

A slightly more complicated test program for your code is here

There are two kinds of time in this program. The heap methods must keep track of how long a method executes. This is actual time or elapsed time, requested from the operating system by the nanoTime method.

Your program keeps track of the time in the schedule, which is simulated time. Do not confuse the two! The elapsed time is in nanoseconds. The simulated time is in arbitrary units: the example file uses 1/10 of an hour as the unit, but for your own examples, you can decide what units to use (minutes, seconds, hours, days, or anything else).

https://docs.oracle.com/javase/8/docs/api/java/lang/System.html#nanoTime--