Homework answers / question archive / Homework # 14 You will implement a min-heap structure using two different data structures: an array (as in the textbook) and a tree (as in the activity)

Homework # 14 You will implement a min-heap structure using two different data structures: an array (as in the textbook) and a tree (as in the activity)

Computer Science

Share With

Homework # 14
You will implement a min-heap structure using two different data structures: an array (as in
the textbook) and a tree (as in the activity). Please read Chapter 10.1 in the textbook, and the
section on representing a complete binary tree with an array (Section 9.2, first three pages).
https://classroom.github.com/a/GyfItoYL
1 Concerning the CompleteTree ADT
For this homework, you will implement two different representations for complete trees. Both
provide the same interface: CompleteTree. A complete (binary) tree as explained in the textbook
(see page 457, or p. 447 in the 3rd ed.), is a binary tree in which every level is completely filled
except (possibly) the last, and that is filled left to right. The shape of the tree is completely
determine by the number of elements it has in it. Such a tree is balanced which makes algorithms
that depends on the height of the tree more efficient than they would be if the tree was unrestricted.
The interface CompleteTree is generic and has an element type E. A complete tree has the
following methods:
size() Return the number of elements. The isEmpty() method is defined to return true if the
size is zero.
root() Return the “location” of the root of the tree. Precisely how locations are defined depends
on the implementation.
last() Return the “location” of the last element of the tree.
add(E elem) Add a new element to the “ned” of the tree and return its “location”.
remove() Return the last element (value) and return it.
A location satisfies the CompleteTree.Location<E> interface which provides the following methods:
get() Return the element at this location.
set(elem) Change the element at this location.
parent() Return the parent location of this location.
child(boolean) Return the left child (or right child) respectively if the boolean is false (or
true).
left() and right() are defined using child.
1.1 Concerning the ArrayCompleteTree implementation
The first implement described here is the ArrayCompleteTree which represents the tree as an array
of all the elements. The elements are listed in order, so for example the tree in the top of the next
diagram, we have the (dynamic) array shown on the bottom:
Fall 2022 page 1 of 4
CS 351 / CST 751: Data Structures & Algorithms Homework #14
G
D
E C
A
B
A D B G E C (unused)
The ArrayCompleteTree will use a location class with an integer to represent locations. The integer
will be one-based rather than zero-based. This makes figuring out one’s parents and children easier.
For example, location 3 has children 6 and 7. The lock test checks that you figured out the pattern.
The array representation is very compact, and is the usual representation of a min-heap.
1.2 Concerning the TreeCompleteTree implementation
The TreeCompleteTree implementation represents the complete tree and a tree of nodes which
pointers to the parent, and the left and right children. This makes it easier to get to these three
relatives compared to the array location. But finding a particular node is tricky. The activity helps
you develop an algorithm for locating (say) the 45th node in the tree. The locked tests check that
you have learned it.
We implement the invariant checkers for both implementations of CompleteTree. Do not change
them.
2 Concerning the MinHeap class
Next we build a min-heap using a complete tree. You will need to use the interface methods—no
sneaking a peek at the data structure!
Chapter 10.1 (pages 521ff, or 511ff in the 3rd ed.) describes the algorithm needed. You need
what the textbook calls “re-heapification upward” (my term is “sifting up”) for addition and “reheapification
downward” (“sifting down”) for removal. The locked tests check that you can do
these processes on paper before you try to implement them in code. The second algorithm is much
harder than the first. (The instructor had two bugs in his first implementation which were only
found after he wrote the tests.)
We provide a large number of tests: the usual ADT tests (TestMinHeap), exhaustive tests,
random tests and efficiency tests.
For this class, we also ask you to implement the invariant checker. We have the usual internal
tests for this code. You should probably do this part first.
Fall 2022 page 2 of 4
CS 351 / CST 751: Data Structures & Algorithms Homework #14
3 What you need to do
1. Do the online activity for this week.
2. Unlock all tests.
3. In either order:
• Complete the implementation of ArrayCompleteTree. Pass all the tests for this class.
• Complete the implementation of TreeCompleteTree. Pass all the tests for this class,
plus the first ten internal tests.
Do the one that looks more intuitive or easier to you first. If you’re not sure, try the “array”
one first; the code is simpler. We implement the invariants for you. Make sure to benefit
from this by asserting the invariant appropriately.
If you let Eclipse create stubs for the methods, you will find that it chooses a very verbose
return type for methods returning a location. Each of the complete tree implementations
has their own implementation of the Location interface and we recommend you change the
return type to return this specific type (which will not need angle brackets).
4. Complete the invariant check for MinhHeap. Pass all remaining internal tests.
5. Complete all but removeMin in the MinHeap class. Pass all the TestMinHeap tests up to the
last testE test.
6. Complete the removeMin method and pass all the remaining (testF) tests.
7. Check your code with TestExhaustive.
8. Check with even more tests using random testing.
9. Check the efficiency with TestEfficiency.
4 Files
Your Homework #14 repository includes the following files in the src folder.
AbstractTestCompleteTree.java Abstract class for testing CompleteTree implementations.
Do not attempt to run this test suite.
TestArrayCompleteTree.java Test suite for the dynamic array implementation of Complete-
Tree.
TestEfficiency.java Efficiency tests for MinHeap; it tests both the array and tree-based implementations
of CompleteTree.
TestExhaustive.java Testing of MinHeap used for sorting sequences of length up to six.
TestImnternals.java Tests for the MinHeap wellFormed method.
TestMinHeap.java ADT tests for the MinHeap class.
TestTreeCompleteTree.java Tests for the tree implementation of CompleteTree.
Fall 2022 page 3 of 4
CS 351 / CST 751: Data Structures & Algorithms Homework #14
UnlockTest.java Unlock tests before running them.
edu/uwm/cs351/CompleteTree.java The CompleteTree interface.
edu/uwm/cs351/ArrayCompleteTree.java The (incomplete) dynamic array implementation
of the CompleteTree interface.
edu/uwm/cs351/TreeCompleteTree.java The (incomplete) tree node implementation of
the CompleteTree interface.
src/edu/uwm/cs351/MinHeap.java The (incomplete) implementation of the min-heap data
structure over a complete tree.
There are random testing for MinHeap and some helper classes in the JAR file.
Fall