Assignment 5: Heaps & Priority Queues
COMP 2140, Fall 2021
Due: Tuesday 7 December 2021 at 5:00 p.m
Instructions
You must complete the “Honesty Declaration” checklist on the course website before you can submit
any assignment.
Assignments must follow the programming standards document published on UM Learn.
After the due date and time, assignments may be submitted, but will be subject to a late penalty. Please
see the course outline document published on UM Learn for the course policy for late submissions.
If you make multiple submissions, only the most recent version (the last submission) will be marked.
We strongly encourage you to submit early!
These assignments are your chance to learn the material for the exams. Code your assignments inde-
pendently. We use software to compare all submitted assignments to each other, and pursue academic
dishonesty vigorously.
You can get help from the T.A. during your lab section and from the instructors and from the course
Assignment 5 discussion forum on UM Learn. You can discuss general topics related to the assignment
with fellow students or other people, but you cannot discuss the solution to the assignment with them.
You cannot copy code from anywhere except COMP 2140 class notes, unless we tell you otherwise. For a
full discussion of our expectations for individual work on this assignment, see the Department of Compute
Science’s expectations webpage.
Your Java program must compile and run upon download, without requiring any modifica-
tions. The marker will not fix your program’s problems.
See also the “Hand in” instructions at the end of this assignment
Part 1 (Programming): Waiting to See a Doctor at an ER
Objective: To simulate patients in an Emergency Room (ER) waiting room.
The application and the file you will complete: The file A05.java contains an incomplete application
that simulates patients a
iving at and leaving an ER.
The application creates a priority queue to represent the waiting room of the ER for a hospital. Then it
andomly generates some events:
A new patient a
ives at the ER. The triage nurse assigns the new patient the next available patient ID
and an appropriate priority (based on the patient’s complaint and condition). The patient then waits in
the waiting room.
The highest-priority patient leaves the waiting room to see a doctor.
A patient leaves the hospital without seeing a doctor.
A patient’s condition changes, so the triage nurse changes the patient’s priority.
1
https:
sci.umanitoba.ca/cs/expectations
After all the randomly-generated events have been handled, the application prints out some statistics.
Representing a patient and the waiting room: A patient is represented by a Patient object, which
contains a patient ID and a priority (both ints). You can get the ID or the priority, and you can change a
priority.
The waiting room is represented by a TriagePriorityQueue, which is implemented as a max heap with all
the usual methods, plus some non-standard methods. The heap a
ay in this implementation is an a
ay of
Patient objects.
The TriagePriorityQueue methods you will write: You will write the bodies of two non-standard methods
in TriagePriorityQueue to complete the application. Do not change anything else in the file.
Method isHeapOrdered needs to return true if the calling TriagePriorityQueue a
ay is in heap orde
and false if it isn’t. It has to check that every parent is in heap order with respect to its children (o
child, if it only has one).
Method changePriority is passed the ID number of a patient in the waiting room and a new priority fo
that patient. This method has two parts: a non-standard part (finding the patient with the given ID in
the heap in a linear search and changing that patient’s priority to the new priority) and a standard part
(restoring heap order). Hint: Use already-written helper methods to find the patient and to restore heap
order — you just have to figure out when and how to call them.
In both these method bodies, if there is already a TriagePriorityQueue method to do something you need to
do, then you should use the existing method. So look at the existing methods and do not duplicate code!
Hand In: To submit the programming part of the assignment, upload the specified file to the Assignment 5
folder on the course website. Verify that the submission worked. (See the detailed hand-in instructions in the
“COMP2140-HandIn-Instructions” document under “General Information” in the content
owser of the course
website on UM Learn.)
Submit ONE .java file, which must be named A5
your first name>.java (e.g.,
A5CameronHelen.java).
Do not submit .class or .java~ files (or compressed files or directories)!
The marker will not edit your file in any way, so make sure it will compile and run for the marker.
Make sure your file does not specify a package at the top!
Part 2 (Written): Operations on Leaf-based 2-3 Trees & Heaps
Objective: To practice basic operations on leaf-based 2-3 Trees and Heaps.
Leaf-based 2-3 Trees: For each of the following trees, using the insertion algorithm for leaf-based 2-3 tree
described in the pre-recorded lectures, insert 2, then insert 15, then insert 25, then insert 35 (in that order). It
suffices to draw the final tree for each case.
7, 26
4
3 6
14, 20
XXXXXXXXXX
29
27 31
Tree A
76
53
44
39 48
61
58 72
91
84
79 88
97
95 99
Tree B
2
4, 8
2
1 3
6
5 7
10
9 14
Tree C
8Tree D
Heaps:
1. Draw the heap tree represented by the following heap structure:
heap XXXXXXXXXX XXXXXXXXXX
XXXXXXXXXX XXXXXXXXXX
10heapSize
2. Insert 55, 19, 36, and 62 (in that order) into the above heap. Draw the heap tree and the heap a
ay afte
all insertions are completed.
3. Consider a heap stored in an a
ay heap = [20, 12, 18, 9, 3, 16, 17, 2]. What does the a
ay contain afte
we apply two deleteMax operations? Write down the a
ay content after the first and after the second
deleteMax operations.
4. Indicate whether the following statement is co
ect or not. Provide a
ief justification for your answer.
You should either use an example (with large n) to show the statement is not co
ect or use English words
to prove the statement:
“The deleteMax() operation in a heap of size n, where n is a large number, can take O(1) in the best
case.”
Hand In: You can write/draw your answers on paper OR use a computer program to typeset your answers.
In any case, you should convert your answers (for all written questions) into a single .pdf file (which must be
named A5
your first name>.pdf (e.g., A5CameronHelen.pdf)) and upload the file to the
Assignment 5 folder on the course website.
3