Java代写|COMP 250 Assignment 4

本次加拿大代写是一个Java数据结构的assignment

Introduction

The main purpose of this assignment is to give you some “hands on” experience with a heap implemen
tation of a priority queue. For the heap that was presented in the lectures, users can add and remove
priorities and can access the min priority. However, that heap only stores priorities; it does not store the
objects that have these priorities.1 Such a heap on its own is not so useful since removing the minimum
priority doesn’t help us if we don’t know which object is associated with that priority. Instead, we write a
priority queue class that uses a heap but represents a set of (object, priority) pairs rather than just priorities.
For our example, the objects will be strings. The class also allows one to perform more general operations
such as changing the priority associated with the string object.

In addition to working with a heap, this assignment will also give you some experience working with
a hash map. The reason you need a hash map is given below.

ERPriorityQueue

Imagine the emergency room (ER) of a hospital. Patients who come to the ER are assessed (triage). We
associate the urgency of the patient’s problem with a single value: the priority.2 As in the heap lectures, we
use a min heap to cater to patients with more urgent situations first. So three patients with priority values
say 3, 4, 8 would be seen in that order. We use double valued priorities since we want to have flexibility,
for example, to add a patient with priority 3.2 between patients with priorities 3 and 4. You should assume
the priorities are always be strictly greater than 0.

The ERPriorityQueue class allows us to organize (name, priority) pairs using nodes which are stored
in a heap. Each node in the heap is an instance of a Patient class which has two fields (name, priority).

The heap implementation will use an ArrayList of these Patients. The Patient class is given to you in the
starter code. For grading purposes, we have included a toString() and equals() method in the Patient class.

For technical reasons having to do with the grader, we have also made Patient a static inner class.

The ERPriorityQueue class has two fields: an ArrayList of Patient objects called patients and a
HashMap nameToIndex. Both of these fields are public for grading purposes. The HashMap name
ToIndex is defined as follows: the key is a string and the value is the index of that string in the ArrayList.

This allows us to find a patient (given their name) in the priority queue.

The ERPriorityQueue class has many methods. Some of the methods are already implemented for you,
namely a constructor, parent(), leftChild(), rightChild(). The rest are described below, and your task will
be to implement them.

Heads up: if you read about heaps, you will find that one often refers to the priorities of a heap as
“keys”. However, in our example, we also work with a hashmap which has a set of (key,value) pairs, where
the key is the patient name. Using the term “key” for both the priority and the name would be confusing.

So in this assignment, we use the term “key” only when referring to the names in the namesToIndex map.

Your Task

Implement the following methods in the ERPriorityQueue class. The starter code contains the method
signatures for all of these methods. Note that some of these methods would naturally be private helper
methods; we make them all public to simplify the grader implementation. We also suggest that you add
your own helper methods, in particular, swap(), isEmpty(), isLeaf().

You may assume that your methods will be tested on valid inputs only e.g. indices that correspond
valid slot locations in the ArrayList for the first two methods below. However, for testing purposes, you
may find it helpful to add your own checks for validity.

• upHeap(int index) (10 points) – returns nothing (void); performs the upHeap operation starting at
the given index. Your implementation should have worst case time complexity O(log2 n).

• downHeap(int index) (10 points) – returns nothing (void) ; performs the downHeap operation
starting at the given index. Note that the method signatures of upHeap and downHeap are slightly
different from the one given in the pseudocode in the lectures. Your implementation should have
worst case time complexity O(log2 n).

• contains(String name) (5 points) – returns a boolean, indicating whether the given string (patient
name) is in the heap. Your implementation should have time complexity O(1).

• getPriority(String name) (5 points) – returns a double which is the priority associated with the
given patient name; all patient priorities will be greater than 0; return -1 if the given name does not
correspond to a patient. Your implementation should have time complexity O(1).

• peekMin() (3 points) – returns the name of the patient with minimum priority; returns null if the
queue is empty. [Updated: Nov 20.] Your implementation should have time complexity O(1).

• getMinPriority() (2 points) – returns the minimum priority of all patients in the queue; returns -1 if
the queue is empty. Your implementation should have time complexity O(1).

• removeMin() (10 points) – returns a string – removes the patient that has the minimum priority and
returns their name; returns null if queue is empty. Your implementation should have worst case time
complexity O(log2 n).

• add(String name, double priority) (10 points) – adds a new patient to the queue; returns a boolean,
indicating whether or not the name was added; return false only if the patient is already in the queue;

Your implementation should have worst case time complexity O(log2 n).

• add(String name) (5 points) – adds a new patient to the queue but now the priority is a default,
namely the double value POSITIVE INFINITY [Updated: Nov. 22]. Likewise, it returns a
boolean, indicating whether or not the name was added; return false only if the patient is already in
the queue. Your implementation should have worst case time complexity O(1). [updated: Nov. 23]

• remove(String name) (10 points) – removes the patient from the priority queue; it returns a boolean:
true if the patient with that name was indeed in the queue and false otherwise;

Your implementation should have worst case time complexity O(log2 n). [Updated: Nov. 22] Sim
ilar to the removeMin() method from the lecture, it should replace the node to be removed with
the last element of the arraylist. Then, it must only modify the ancestors and/or descendants of the
removed node.

• changePriority(String name, double newPriority) (10 points) – modifies the priority of the patient
and adjusts the priority queue, if necessary; returns a boolean – returns true if the patient is indeed
in the heap and false otherwise

The idea of this method is that it can happen that the priority of patients in the waiting room can
change over time. The patient may have a test done at the hospital (blood test, x-ray, covid, etc) and
may get a positive or negative result that changes their priority. Your implementation should have
worst case time complexity O(log2 n). [Updated: Nov. 22] In particular, it must only modify the
ancestors and/or descendants of the node for which we changed the priority and must have a best
case behavior of O(1), e.g. if no modification is required.

• removeUrgentPatients(double threshold) (10 points) – removes the patients whose priority value is
less than or equal to the given threshold; you can assume that the threshold is positive. Recall that
having a low priority value means having a “high priority” i.e. urgent. [Updated: Nov 23] The
method returns an ArrayList of the urgent patients that have been removed. Your implementation
should have worst case time complexity O(n log2 n).

• removeNonUrgentPatients(double threshold) (10 points) – removes the patients whose priority value
is greater than or equal to the given threshold; you can assume the threshold is positive. [Updated:
Nov 23] The method returns an ArrayList of the non-urgent patients that have been removed. Your
implementation should have worst case time complexity O(n log2 n).


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: itcsdx@outlook.com  微信:itcsdx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论