COMP 2140 Assignment 5: 2-3 Tree Insertions and Heap Sort
Helen Cameron and Stephane Durocher
Due: Wednesday December 3 at noon
Programming Standards
When writing code for this course, follow the programming standards, available on this course's website on
Desire2Learn. Failure to do so will result in the loss of marks.
Question 1: Leaf-based 2-3 Tree Insertions
File A5Part1.java contains a nearly-complete program that inserts values into a leaf-based 2-3 tree, searching
for those values after insertion and validating the leaf-based 2-3 tree (to ensure that everything was done
properly). Note that no duplicate values are permitted in this version. The 2-3 tree class and the associated
node class used in A5Part1.java are the same ones used in Lab 5:
How TwoThreeNodes look: The following three pictures are taken from Lab 5.
An interior (non-leaf) node
with ONE index value and TWO
children; for example:
parent
parent of the node
int numValues 1
int[] value
37 ??
child
left child
of the node
(keys < 37)
right child
of the node
(37 keys)
?
An interior (non-leaf) node
with TWO index values and
THREE children; for example:
parent
parent of the node
int numValues 2
int[] value
4 9
child
left child
of the node
(keys < 4)
middle child
of the node
(4 keys < 9)
right child
of the node
(9 keys)
A leaf has NO children and only
one data item, so the child array
is not allocated for a leaf node
and the value array has length 1.
For example, a leaf looks like the
following:
TwoThreeNode parent
parent of the leaf
int numValues 1
int[] value 49
TwoThreeNode[] child ?
You are asked to complete the insertion code (details below). Remember that the tree is a leaf-based
2-3 tree, so that data items are stored only in the leaves, each leaf stores exactly one data item (in this case,
just an int) and each interior (non-leaf) nodes store one or two index values (not data item(s)) to guide
searches to the leaves.
The Method That You Must Write:
Most of the insertion code is written for you, except the body of the method splitsThenInsert, which is
passed a new leaf to add to the leaf-based tree and an existing leaf that the new leaf should be inserted
immediately beside. The method does not return anything.
Here's what splitsThenInsert should do:
1curr = the existing leaf;
currSibling = the new leaf;
decide which key should be copied to the parent above them as an index value;
// Do any splits that are needed
while curr isn
t the root (i.e., has a parent)
and
curr
s parent doesn
t have room for currSibling
f
create a new node, currParentSibling, to be used in the split;
call method split (already written for you) to split curr
s parent,
which returns to you the index value to push up to curr
s
grandparent (along with currParentSibling);
curr = curr
s parent;
currSibling = the new node, currParentSibling;
g // end while
// Finish, after all necessary splits are completed
if curr is the root
// we split the root!
create a new root with curr and currSibling as children and the index value
returned from the last split;
else
// the parent of curr has room for currSibling
call method addChildToParentWithRoom (already written for you)
to add currSibling to curr
s parent, along with the index value
returned from the last split;
Do NOT change anything else in the le other than the name of the public class and the le name
(to comply with the hand-in instructions below).
Question 2: Heaps
Take the solution to the sorting assignment (Assignment 1), which is available on D2L (or you can use your
own if you got a good grade on the assignment and you x any problems that the marker pointed out). Add
a new sorting algorithm, heap sort, to the testing. Run the same tests as speci ed in Assignment 1 on your
program.
To add heap sort, you need to add a Heap class to the le. In your Heap class, you need to declare the
heap array and the size. The constructor should accept an array (the array to be sorted) as a parameter, and
set heap to point at it, and set the size to 0 (because the array is not in heap order yet). In this application,
it is probably easiest if your heap simply stores ints (i.e., an int priority with no other data associated with
it).
The heap sort method should be in the Heap class | see the description of heap sort below. You should
also write a deleteMax/extractMax method that uses a private helper method named siftDown/reheapDown.
Method siftDown/reheapDown should accept one parameter, the array index of the item that should be
sifted down. Method deleteMax/extractMax will always pass 0 to the parameter of siftDown/reheapDown.
Method heapify/buildHeap, however, also uses siftDown/reheapDown, but does not always pass 0 to the
parameter of siftDown/reheapDown.
Heap sort works by creating a heap from the array. Then it extracts the items (using deleteMax/extractMax)
in sorted order, from largest to smallest. An extraction causes the heap to use one fewer position in the
array (the position immediately after the last leaf of the heap), and that position is where the extracted item
2belongs in sorted order.
Heap sort works as follows:
First, turn the array to be sorted into a (max) heap array using method heapify/buildHeap on it and
then setting the size to the length of the array.
Then perform the following loop:
while heapSize > 1
do a deleteMax/extractMax on the heap, which returns a value (and decrements the size);
put the value in the array at position size
(which was just made empty by the deleteMax/extractMax);
To use heap sort, you must rst create a heap using the constructor that accepts the unsorted array as
a parameter. Then call heap sort on the heap. When heap sort returns, the array is in sorted order.
Hand-in Instructions
Go to COMP2140 in Desire2learn, then click \Dropbox" under \Assessments" at the top. You will nd a
dropbox folder called \Assignment 5". Click the link and follow the instructions. Please note the following:
Submit ONE .zip le named A5<your last name><your student id>.zip. The .zip le must contain
TWO .java les.
The rst .java le must contain all the source code for Question 1 (on 2-3 trees) The .java le must be
named
A5Part1<your last name><your student id>.java (e.g., A5Part1Cameron1234567.java).
The second .java le must contain all the source code for Question 2 (on heap sort) The .java le must
be named
A5Heap<your last name><your student id>.java (e.g., A5HeapCameron1234567.java).
Please do not submit anything else.
We only accept homework submissions via D2L. Please DO NOT try to email your homework to the
instructor or TAs.
We reserve the right to refuse to grade the homework or to deduct marks if these instructions are not
followed.
Honesty Declaration
Your Assignment 5 (and any other work in this course) will not be marked unless you have already handed
in the blanket honesty declaration.
3