Programming question for Homework 1: Ternary Heaps

Implement a priority queue class, and use this class to implement a HeapSort algorithm that sorts Vector objects. The priority queue is implemented as a nearly-complete ternary tree, and is encapsulated in a class (called TernaryHeap) that extends the Vector class. The tree used to represent the heap is stored in the Vector such that the root of the tree is stored at position 0 of the Vector, and, for every i = 0..(size()-1), the left, middle and right children of the element stored at position i, if they exist, are stored at positions 3i+1, 3i+2, and 3i+3, respectively. For every element of the heap, the priority of this element must be higher than or equal to that of its children. To compare the priorities of two heap elements an instance of a class that implements the PriorityComparator interface is used.

You should implement the following methods of the TernaryHeap class (described in the starter code):

• buildTernaryHeap()
• extractHighestPriority()
• insertElement()

You must also implement the following method of the TernaryHeapSort class:

• sort()

The worst-case time complexity of buildTernaryHeap() should be O(n), the worst-case time complexity of extractHighestPriority() and insertElement() should be O(logn), and the worst-case time complexity of sort() should be O(nlogn), where n is the size of the heap.

To mark your assignment, we will test the above methods using a tester routine that is more thorough than the sample TernaryHeapTester class provided. The sample TernaryHeapTester class that we provide is very basic; running it successfully does not guarantee that your code is correct or will pass our marking tester routine. You are encouraged to derive your own test cases. Each method gets 5 marks if it works correctly, and gets 0 marks otherwise.

For more details, including exact specifications of the methods that you should implement, see the starter code. All of your work must be done inside the TernaryHeap class and the TernaryHeapSort class, where indicated by comments that start with: "// TODO:". You may also add appropriate private instance variables or helper methods.

• PriorityComparator.java
• TernaryHeap.java
• TernaryHeapSort.java
• TernaryHeapTester.java

Submission Instructions

1. Submit your code using the "submit" mechanism on CDF (by 5:30pm on the due date). The CDF FAQ contains general instructions for submitting your code electronically (under the "Submitting Work" section).


2. Submit only the .java files TernaryHeap.java and TernaryHeapSort.java of the starter code (after you have implemented the missing parts) to the directory called PGM1. All the code that you implement should be inside these two files.


3. Do not submit any other files, and in particular, do not submit any class files. If you do, we will delete them before we compile your code.


4. Do not submit any printout of the code.


5. Do not rename the files TernaryHeap.java and TernaryHeapSort.java, or any of the methods and variables found in our starter code.


6. Write your name, student number and CDF username in a comment at the top of the TernaryHeap.java file. If you have a partner, you should also write the corresponding information about your partner.


7. We will compile your code by typing "javac TernaryHeap.java" and "javac TernaryHeapSort.java", and we will test the resulting .class file(s) using our own tester code (which is similar to, but more thorough than, the tester code that we provide as part of the starter code).


8. Your code must compile and run on the CDF Unix/Linux system. Test it there! Programs that do not compile and run get 0 marks.