Java代写 | 数据结构代写 | 算法代写 – CPS 350 Assignment 4

java代写 | 数据结构代写 | 算法代写:这是一个利用java进行heap等数据结构复现的代写

1. Purpose

The purpose of this assignment is to implement priority queues.

2. Description

2.1. Implementation (40 points for 3-Heap, 50 points for d-way Heap)

Your main task is to implement two priority queues. All two implementations should implement
the provided PriorityQueue interface (include implements PriorityQueue in your Java code),
which means they should work with priorities of type double and there are no corresponding
items attached to the priorities. Your implementations should be as fsollows:

• A class ThreeHeap that implements a min-heap where each non-leaf node has 3 children.
You should still use a contiguous portion of an array to store the conceptual complete
tree. We suggest you make a copy of BinaryHeap class (discussed in class) and make
changes as necessary.

• A class DWayHeap that implements a d-heap where d is the number of children for nonleaf
nodes. Your class should implement the same priority queue interface and it should
use a contiguous array portion as in your first implementation. It should include an empty
constructor and additional constructor that takes d as an argument, work correctly for
any d greater than or equal to 2, and use d as the number of children for nodes.

Put your two implementations in two separate Java files, and
Your priority queues should allow duplicates. That is, two or more copies of the same value
should be allowed to exist in the heap at the same time. For example, if you call deleteMin and
you have {3.0, 3.0, 6.0, 7.0} in the heap, it would just return one of the 3.0 values, then on the
next deleteMin it would return the other 3.0. It does not matter “which” 3.0 is returned first.
According to our definition of priority queue, what must be guaranteed is that both 3.0 values
will be returned before a 6.0 or 7.0 is returned, and that the 6.0 would be returned before the 7.0.

Your implementations should automatically grow as necessary. (If interested, you may also have
them shrink when appropriate; this is optional.) For any arrays, you should start with a small
array (say, 10 elements) and resize to use an array twice as large whenever the array becomes
full, copying over the elements in the smaller array. Do the copying with a for loop rather than
any Java library methods (even though using the library is how one would normally do it). You
may use the length field of an array as needed.

Be sure to test your solutions thoroughly. For instance, you may generate 1000 random numbers,
insert them into a priority queue, and keep deleteMin() as long as the priority queue is not empty.
Part of the grading will involve thorough testing including any difficult cases. For this
assignment, we will be grading more strictly for things like style and efficiency.

2.2. Report (10 points)

The questions include comparing the actual run-time of your implementations. We would expect
the reports to be at least a couple of pages long, quite possibly longer to have room for relevant
graphs or tables.

Submit a report.pdf file, answering the questions below:

1. (4pts) List any difficulties you have during implementation. Did you start this
assignment early?

2. (2pts) What is the worst case asymptotic running time of isEmpty, size, insert, findMin,
and deleteMin operations on all your 3-heap implementations? For this analysis you
should ignore the cost of growing the array. That is, assume that you have enough space
when you are inserting a value.

3. (2pts) Which of your two implementations would you recommend to someone who needs
to use a heap? Why is that one preferred? Are there any conditions under which you
might suggest using your other implementations?

4. (2pts) Briefly discuss how you went about testing your two heap implementations. Feel
free to refer to your testing files, which you should submit.

3. Grading notes

If your program does not compile, you receive zero points for that program. Additional

1. (5 points) Your code does not follow the style guide discussed in class/textbook.

2. (30 points) Your code does not have author name, date, purpose of this program, comments on the variables and methods, etc.

4. Turn in

Zip the entire project and submit the ZIP to isidore, where you should include:



• Any additional Java files needed, if any.

• The Java files you used to test your implementations.

• report.pdf for bonus points, containing answers to Questions in 2.2.

• (offered at isidore/Assignments)

• (offered at isidore/Assignments)


电子邮件地址不会被公开。 必填项已用*标注