In Part $1$ of this assignment, you will be implementing the PriorityQueue interface using a

generic array$-$based Heap data structure. A reference$-$based implementation is provided for you

$($LinkedPriorityQueue$.$java and A$5$Node.java$),$ so you can run the tester and compare the run

times of the two implementations.

In Part $2,$ you will implement a small application modeling an Emergency Room at a hospital

$($called EmergencyRoom.java$).$ The EmergencyRoom class uses the HeapPriorityQueue you

implement from Part $1.$

The automated grading of your assignment will include some different and additional tests to

those found in the A$5$Tester.java file, as it does not include a comprehensive set of tests for each

method. You are expected to write additional tests until you are convinced each method has full

test coverage. The displayResults and test coverage videos provide more information about

code testing.

OBJECTIVES

Upon finishing this assignment, you should be able to:

o Write an implementation of an array$-$based Heap

o Implement a compareTo method to specify the order of two Comparable objects

o Write code that uses an implementation of the Priority Queue ADT

SUBMISSION AND GRADING

Attach HeapPriorityQueue.java, Patient.java, and EmergencyRoom.java to the BrightSpace

assignment page. Remember to click submit afterward. You should receive a notification that your

assignment was successfully submitted.

If you chose not to complete some of the methods required, you must provide a stub for the

incomplete method$($s$)$ in order for our tester to compile. If you submit files that do not compile

with our tester, you will receive a zero grade for the assignment. It is your responsibility to ensure

you follow the specification and submit the correct files. Additionally, your code must not be

written to specifically pass the test cases in the tester, instead, it must work on all valid inputs.

We may change the input values during grading and we will inspect your code for hard$-$coded

solutions. This video explains stubs.

Be sure you submit your assignment, not just save a draft. All late and incorrect submissions will

be given a zero grade. A reminder that it is OK to talk about your assignment with your classmates,

but not to share code electronically or visually $($on a display screen or paper$).$ Plagiarism detection

software will be run on all submissions.

ASSIGNMENT $5$

$($PRIORITY QUEUES$)$

OVERVIEW:

The LinkedPriorityQueue implementation provided does not make use of the O$($logn$)$ heap

insertion and removal algorithms we discussed in lecture. Instead, when an item is inserted, the

queue is searched from beginning to end until the correct position to insert the item is found.

The HeapPriorityQueue insertion implementation you write should improve on this

implementation so that the insert runs in O$($logn$)$ using the bubbleUp algorithm covered in

lecture. Similarly, your removeMin should use the bubbleDown algorithm.

Part $2$ asks you to complete the implementation of the JobApplication and ApplicationManager

classes. Using these classes with a priority queue will give you experience building a small

application that models a system that helps prioritize job applications from a large application

pool. In the system, all job applications are given priority depending on how suitable their

application looks. All job applications submitted to the system are stored in the priority queue

such that high priority applications are handled $($ie$.$ removed from the priority queue$)$ first.

Note that the priority queue in this assignment extends the Comparable class. All classes that

implement Java$$s Comparable interface must provide an implementation of the compareTo

method, which is a method that allows us to compare two objects and return a number that

represents which of the two should come first when sorted. The compareTo method is helpful for

a priority queue as it can be used to compare priority values to determine how items should be

ordered within the priority queue.

When implemented correctly, an object$$s compareTo method has the following behaviour:

$$ returns $0$ if the two objects being compared are ordered equally

$$ returns a negative value if this object should be ordered before the other object

$$ returns a positive value if this object should be ordered after the other objec