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 trees T0, T1 and T2 are shown below:

Trinomial tree examples

The trinomial tree Tk has the following properties:

A trinomial heap H is a set of trinomial trees that satisfies the following two properties:

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.

Binomial heap example

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:

  1. 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.

  2. 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.

  3. Do not submit any printout of the code.

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

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

Hints: