Reference no: EM13220634

Programming question for Homework 1: Trinomial Heaps 
Purpose: 
In class, you learned about binomial heaps. In this question, you will investigate another type of priority queue, which we will call a trinomial heap. The goal of the assignment is to make you more familiar with both binomial heap and trinomial heap operations, and how priority queue data structures are programmed. 

Trinomial heaps:
In order to define a trinomial heap, we must first define a trinomial tree. A trinomial tree can be defined recursively: 

the trinomial tree T0 consists of a single node 
the trinomial tree Tk consists of three trinomial trees Tk-1 that are linked together: the roots of two trees are the leftmost and second leftmost children of the root of the third tree. 

The trinomial trees T0, T1 and T2 are shown below: 


The trinomial tree Tk has the following properties: 

tree Tk has 3k nodes, 
tree Tk has height k, and 
the root of tree Tk has 2k children. 

A trinomial heap H is a set of trinomial trees that satisfies the following two properties: 
Each binomial heap obeys the min-heap property, and 
For any nonnegative integer k, there are at most two trinomial trees in H with height k. 
Task: 
The file THeap.java is an implementation of a binomial heap. You must modify the code in the file THeap.java to turn it into a trinomial heap implementation. In particular, the operations insert, minimum, extractMin and decreaseKey must all work correctly for a trinomial heap. It is your task to figure out what code needs to be changed and to change it. 

Interface file:
To assist you with this question, we are also providing a file Heap.java to test the THeap methods. Do not submit this file. Once you have downloaded the file THeap.java and Heap.java, you can use the command javac Heap.java to compile the code, and use the command java Heap to run the code. (This is exactly how the marker will compile and run your program!) 
About the print command:
The print command will print a binomial heap in the following format: 
key = 9, degree = 0
key = 3, degree = 2
key = 4, degree = 1
key = 6, degree = 0
key = 5, degree = 0

The indentation represents the depth of a node in the binomial tree. Thus, all siblings have the same amount of indentation. The parent of a node x is the last node printed above x with one less indent. For example, in the printout above, the nodes with the keys 4 and 5 are the children of the node with key 3, and the node with key 6 is the child of the node with key 4. A drawing of the binomial heap is given below. 

Testing:
We will test your THeap.java file using a secret set of test cases. (You will not be surprised to learn that we will be mainly testing the insert, minimum, extractMin and decreaseKey methods to ensure that your code is correct.) 

Do not change the names of the methods in the file THeap.java or any of the input parameters or return types. We will not be able to call the methods if you change them! Also, do not change any code in the print method! You may add new methods, however, if needed. 

If your code does not compile on the UTSC computer system, you will receive a mark of 0 on the programming component. 

Submission instructions:
Submit your code using the "submit" mechanism on fissure (by 6:00pm on Sunday, June 1). Use the following command from the directory containing your solution:
submit -N p1 cscb63s THeap.java
The command "man submit" contains general instructions for submitting your code electronically.

Submit only the file THeap.java. Do not submit any other files, and in particular, do not submit any class files. Any other files submitted will be deleted before we test your program.

Do not submit any printout of the code.

Fill in your name, student number and login name in the comment at the top of the THeap.java file.

Your code must compile and run on the fissure system. Test it there! Programs that do not compile and run get 0 marks.

Hints:
Compare the definitions of trinomial tree and trinomial heap with the deifnitions of binomial tree and binomial heap on pages 457 and 459 of the textbook (Chapter 19). 
Make sure you understand the output of the print command. 
Think carefully about what needs to be changed before making any changes!