In java, Design and implement a priority queue of processes, whose entries consist of an invariant integer ID and a changeable integer priority. (If we do this in operating systems, the process record will have lots of other fields associated with it, but these wont affect the piece were building now.) For this assignment, we will assume that maximum priority wins (a max-priority queue), but the changes to create a min-priority queue are small.

You can use a class variable, static int processNumber to generate new process IDsstart at 0 and increment each time you create a new process.

The priority queue consists of (1) a structure holding the list of active processes, and (2) a max-heap (stored as an array) to manage the priorities of those processes. There may be priority ties.

Supported operations

The methods that have to be supported are:

(1) Test if the heap is empty.

(2) Count the number of active processes.

(3) Print the set of active processes, with or without their priorities.

(4) Insert a new process with a specified priority

(5) Observe the maximum priority process, printing the process ID and its priority.

(6) Delete the maximum priority process, returning the process ID.

(7) Increase the priority of a given process by a specified delta.

(8) Decrease the priority of a given process by a specified delta.

(9) Change the priority of a given process to a given value.

(10) Delete an arbitrary process.

You may also want to add a method to create the initial priority queue.

Methods (2), (3), (5) and (6) should return a message if there are no active processes (the heap is empty).

Methods (7)-(10) should fail and return a message if there are no active processes, or if the specified process is not active.

Method (4) should fail and return a message if a process with that ID is already in the priority queue. (While the simplest version of the insert method will use a new process ID, it is also possible to revive an old ID.)

Easy stuff

Testing if the heap is empty is just a check of the heapTop reference for NULL. Returning the process ID and priority uses the heapTop reference and then its processList reference.

Counting the number of active processes can be done in the process list, without using the heap. Printing the active processes (or all processes) can also use the process list. If you need to print the priorities, follow each processs heapLocation reference.

The processList structure

The easiest processList structure is an array indexed by all possible processID (so set a maximum ID). Array entries contain an index in the heap array, heapIndex, which is -1 if the process is not active (not yet created or deleted). If you want to be clever, you can wrap the index around and try to reuse any index set at -1; if no index is -1, then you should return a processTableFull error.

The heap structure

The heap is stored as an array, each of whose entries is a pair of integers: the priority and the processID, which is an index in the process table.

Implementation of the heap operations

There are two responsibilities for each method, other than the obvious. First, restore the heap property, and second (and simultaneously), maintain the ID-to-heap-location invariant.

Restoring the heap property uses the heapDown and heapUp operations: increasePriority and Insert can only use heapUp, decreasePriority and deleteMax can only use heapDown, and changePriority and delete can use either (but not both).

deleteMax: remove the top process from the heap, replace it by the last process

decrement last, heapDown from heapTop

insert: (after checking for duplicates in the processList)

add to heap after last position (and increment last), heapUp

increasePriority: find the process in the heap, modify priority, heapUp

decreasePriority: find the process in the heap, modify priority, heapDown

changePriority: find the process in the heap, compare newPriority to priority

if priority changes, call increasePriority or decreasePriority with difference

delete: find the process in the heap, replace by last process, and decrement last

if priority is greater than parents, heapUp; otherwise, heapDown

Maintaining the linkage: Each time there is a swap, the pair of entries in the corresponding heap positions have to use their processID values to return to the processTable to update the heapIndex value.