本次Java代写是完成堆、树、哈希表等数据结构的编程

COMP3506 Homework 3 – Heaps, Trees, Hashtables

Questions

1. (10 marks) Recall in-place heapsort described in lectures and tutorials, where we build a binary heap in-place

bottom-up within an array. A variant of a binary heap is a quaternary heap which is a heap where nodes can

have (at most) 4 children.

In this question, you will implement in-place quaternary heapsort. This should build a quaternary heap

in-place bottom-up, then use this to sort the array in ascending order.

(a) First, you should implement the helper function quaternaryDownheap in QuaternaryHeapsort.java.

This should perform a downheap operation on a quaternary max heap within an array.

(b) Using this helper function, implement quaternaryHeapsort within QuaternaryHeapsort.java.

(c) State the worst case time and space complexity (in Big-O notation) of all your methods in their Javadoc.

Below is an example visualisation of a quaternary max heap. Note that it is a complete quaternary tree (leaf

nodes of bottommost level are as far left as possible). The array representation of the below heap would be

[9, 2, 5, 7, 5, 1, 0, 2].

Here are some examples of quaternaryDownheap. It works on the array representation of a heap and performs

the downheap in-place.

• Input heap [0, 10, 20, 30, 40] and start index 0 would modify the array to [40, 10, 20, 30, 0].

• Input heap [1, 0, 2, 3, 4, 10, 20, 30, 40] and start index 1 would modify the array to [1, 40, 2, 3, 4, 10, 20, 30, 0].

Note that higher levels (the root node in this case) are not changed.

Notes:

• You should create and use private helper methods to improve readability of your code.

• You will be given no marks for any variant of heapsort that doesn’t utilise a quaternary heap.

2. (10 marks) We will call a binary tree a strong heap1

if it is a complete binary tree and it satisfies the “strong

(max) heap property” as:

• for all nodes x, we have x < parent(x), and

• for nodes x in level 2 or below, we also have x + parent(x) < parent(parent(x)).

In StrongHeap.java, implement isStrongHeap. This takes one argument, the root of a binary tree, and

returns whether the given binary tree is a strong max heap. State the worst case time and space complexity

(in Big-O notation) in the method’s Javadoc.

These are some examples of trees which are and are not strong heaps. The second is not a strong heap because

5 + 5 ≮ 10. The third is not a strong heap because the tree is not complete, despite satisfying the strong heap

property.

Hints and notes:

• As a reminder, the root node of a tree is at level 0.

• A tree with a single node is trivially a strong binary heap.

• Strong binary heaps are a subset of binary heaps.

• If a binary tree is not complete, it cannot be a strong heap. If a tree is complete, you must check the

strong heap property to determine whether it is a strong heap.

• Node values can be negative but not null. Negatives should not be treated specially.

1This is just terminology used here and has no relevance outside this assignment.

3. (10 marks) This question is about comparing binary trees.

To compare two binary tree nodes, we first compare their left subtrees, then compare their values (with

compareTo), then compare their right subtrees. If all of these are equal, then the nodes are equal. Otherwise

the first non-equal comparison in this order is the result of the comparison. To compare the subtrees, you

should recurse and compare them in the same way as described here.

Regarding nulls (e.g. missing left/right children), a null subtree should compare equal to another null, or less

than any non-null subtree.

Implement the BinaryTreeComparator class in BinaryTreeComparator.java. This has a single method

compare which takes two trees x and y then returns −1, 0, +1 if x < y, x = y, or x > y (respectively). State

the worst case time and space complexity (in Big-O notation) in the method’s Javadoc.

Here are some examples of trees and how they compare. The highlighted node(s) are those which determine

the comparison result. Take note of the last case where the null left subtree is less than the non-null left

subtree.

Hints and notes:

• You may add private helper methods if needed, but you should not use any instance variables.

• You can assume that values stored within nodes are not null and implement Comparable (so you can use

the compareTo method).

• You cannot assume the node itself will be non-null. Nulls should be compared as described above.

• You should not perform unnecessary comparisons. For example, if the left subtrees differ, you should

not compare the right subtrees.

• Although the Comparator interface only requires the return value to be negative/zero/positive, here you

must return exactly −1, 0, or +1.

4. (15 marks) A multiset is a collection that extends the idea of a set to have duplicate items. It is able to keep

track of the number of occurrences of each duplicate in the set.

For this question, you will implement LinkedMultiHashSet, a multiset that internally uses a resizing array

and hashing (based on element’s hashCodes) to make most operations run in O(1) average time. In addition

to the ordinary methods for a set, you will need to implement an Iterator which returns elements in a

particular order (see below and Javadoc).

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

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

**E-mail:** [email protected] **微信:**itcsdx

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