COMP3506 Homework 3 – Heaps, Trees, Hashtables
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.
• 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
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
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).
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: [email protected] 微信:itcsdx