- 作业标题：CSCI 2110 - Data Structures and Algorithms - lab 9
- 课程名称：Dalhouse University CSCI 2110 Data Structures and Algorithms
- 完成周期：2天
描述
The objective of this lab is to help you get familiar with the Heap data structure. Review the lecture
notes on Module 8. You will need the following file to complete your work:
Heap.java (the Heap class)
Marking Scheme
Each exercise carries 10 points.
Working code, Outputs included, Efficient, Good basic comments included: 10/10
No comments or poor commenting: subtract one point
Unnecessarily inefficient: subtract one point
No outputs and/or not all test cases covered: subtract up to two points
Code not working: subtract up to six points depending upon how many methods are incorrect. TAs can
and will test cases beyond those shown in sample inputs, and may test methods independently.
Your final score will be scaled down to a value out of 10. For example, if there are three exercises and
you score 9/10, 10/10 and 8/10 on the three exercises, your total is 27/30 or 9/10.
Error checking: Unless otherwise specified, you may assume that a user enters the correct data types
and the correct number of input entries, that is, you need not check for errors on input.
Submission: All submissions are through Brightspace. Deadline for submission: Sunday, November
28th, 11.59 PM
Late Submission Penalty: The lab is due on Sunday at 11.59 PM. Late submissions up to 5 hours
(4.59 AM on Monday) will be accepted without penalty. After that, there will be a 10% late penalty
per day on the mark obtained. For example, if you submit the lab on Monday at 12 noon and your
score is 8/10, it will be reduced to 7.2/10. Submissions past two days (48 hours) after the grace
submission time, that is, submission past 4.59 AM Wednesday will not be accepted.
Exercise 1: Heap Methods
You have been given the Heap class (Heap.java). The Heap class that we have designed is a Max
heap, since the largest key (key with the highest priority) is always at the top of the heap.
a) Add the following methods to the class:
public T findMin()
This method finds and returns the smallest key in the heap. You must search and return the key in an
efficient manner, rather than doing a linear search of all the elements. Note that there could be duplicate
keys – you just need to find one of the smallest keys.
public void replace (T key1, T key2)
This method replaces key1 in the heap with the key2. This would cause the heap to be altered.
Depending upon the new value, that node could sift up or sift down. Take a look at the examples below:
。。。
