Description
Objectives
More practice implementing an interface in Java
Exposure to the Priority Queue ADT
Practice implementing a Heap
Exposure to the Comparable interface
Introduction
This assignment has two parts:
Part 1 asks you to implement the PriorityQueue interface using an array-based Heap data
structure that will store Comparable objects (objects that implement the Comparable
interface). A reference-based list implementation of PriorityQueue is provided for you
(LinkedPriorityQueue.java and ComparableNode.java) so you can run the
Part1Tester and compare running times of the two implementations.
The PriorityQueue implementation provided does not make use of the heap insertion and
removal algorithms we discussed in lecture (that bubble-up and bubble-down, which are very
efficient). Instead, any time an item is inserted, the list must be searched from the beginning to
end until the correct position to insert the item is found, as the priority queue is ordered based on
the item’s priority.
You will implement an array-based heap (HeapPriorityQueue) that is much more efficient
in its insertion and removal of items.
Part 2 asks you to implement the Patient and EmergencyRoom classes. Using these classes
with a priority queue will give you experience building a small application that models an
emergency room in a hospital. Patients waiting to be helped are stored in the priority queue such
that high priority patients are helped (ie. removed from the priority queue) first.
Note that the priority queue in this assignment works with Comparable items. 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 equal
– 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 object
For example:
Integer a = new Integer(7); Integer b = new Integer(9);
a.compareTo(b) returns a negative value. a.compareTo(a) returns 0
String x=new String(“computer”); String y=newString(“science”);
x.compareTo(y); returns a negative value. y.compareTo(x) returns a positive value
Part I
1. Download the files: A5Tester.java, PriorityQueue.java,
HeapPriorityQueue.java, LinkedPriorityQueue.java,
ComparableNode.java, HeapEmptyException.java and
HeapFullException.java.
2. Read the comments in HeapPriorityQueue.java carefully
a. Add the constructors and required method stubs according to the interface
in order to allow the tester to compile.
3. Compile and run the test program A5Tester.java with
LinkedPriorityQueue.java to understand the behavior of the tester:
javac A5Tester.java
java A5Tester linked
Note: the A5Tester is executed with the word “linked” as an argument, similar to how we
added the file name of mazes as an argument for the previous assignment.
This argument allows us to run all of the tests against the LinkedPriorityQueue
file provided for you. You will notice it is extremely slow with larger file input sizes (for
the largest input size we will only test it with the heap implementation).
4. Compile and run the test program A5Tester.java with
HeapPriorityQueue.java and repeat step a and b below
javac A5Tester.java
java A5Tester
a. You will notice the tester crashes. You will need to implement the methods
specified in the PriorityQueue interface one by one until all of the tests also pass
for the HeapPriorityQueue.java implementation of a priority queue.
b. Once all of the tests have passed move on to Part II.
5. You can run the tester on the LinkedPriorityQueue by running as follows:
java A5Tester linked
Notice how much slower it is! It even skips a test and it still very slow!
Part II
For this part of the assignment, you will be creating an application to support the modelling of a
an emergency room in a hospital. You are asked to write the software that will manage handling
patients waiting to be helped based on the priorityLevel of their ailment and their arrivalTime.
Imagine… you are checking people in to an emergency room at a hospital. Each time someone
arrives they get a waiting number ticket (which is a letter followed by numbers), and are asked to
wait until their ticket number is called. You must make sure all high priority patients are helped
before lower priority patients. For example:
o A patient (A) enters with a priority level 3 ailment. You add them to the queue.
o A patient (B) enters with a priority level 1 ailment. You add them to the queue ahead of
the previous person (A), as priority level 1 ailments must be handled first.
o Another patient (C) enters, also with a priority level 1 ailment. You add them to the
queue ahead of person A (also priority level 1) but behind the person B (priority level 1)
because both B and C have the same priority level but C arrived at a later time.
o A doctor is now ready to help a patient, so person B gets helped and leaves the waiting
room (priority queue).
o A patient (D) enters with priority level 2. You add them to the queue ahead of passenger
A (priority level 3) but behind passenger C (priority level 1).
The given a tester A5Tester.java that will test the functionality of your EmergencyRoom
implementation and mimics a scenario similar to the one the above. The classes involved are
represented in the UML diagram below. Read the tester and documentation carefully to help you
understand how the classes you will be writing will be used.
Submission
Submit only your HeapPriorityQueue.java, Patient.java and
EmergencyRoom.java via ConneX.
Please be sure you submit your assignment, not just save a draft. ALL late and incorrect
submissions will be given a ZERO grade.
Even if you choose not to complete all parts of the assignment, you must submit ALL files and
they MUST compile with the full, uncommented tester or you will receive a ZERO grade.
If you submit files that do not compile, or that do not use the correct method names you will
receive a zero grade for the assignment. It is your responsibility to ensure you follow the
specification and submit the correct files.
Your code must not be written to specifically pass the test cases in the testers, instead, it must
work on all valid inputs. We will change the input values, add extra tests and we will inspect
your code for hard-coded solutions.
A reminder that it is OK to talk about your assignment with your classmates, and you are
encouraged to design solutions together, but each student must implement their own solution.
We will use plagiarism detection software on your assignment submissions.
