2.5. Quiz

Quiz 2: Priority Queues

Coding

• Create a class called TernaryHeapQuiz under the main queue package that extends the abstract class AbstractPriorityQueue.

• Each node in TernaryHeapQuiz takes up to 3 children, so it becomes a ternary instead of a binary tree.

• Override the required abstract methods, add(), remove(), and size(), such that both add() and remove() give $O(log_3 n)$.

• Feel free to use the code in BinaryHeap.

Testing

• Create the TernaryHeapQuizTest class under the test queue package.

• Test the correctness of your TernaryHeapQuiz using the testRobustness() method.

• Add more tests for a more thorough assessment if necessary.

Benchmarking

• Compare runtime speeds between BinaryHeap and TernaryHeapQuiz for add() and remove() using the testRuntime() method.

• Create a PDF file quiz2.pdf and write a report that includes the following:

  • A table and a chart to compare speeds between the two priority queues for those two methods, add() and remove(), with respect to different input sizes.

  • A brief explanation of why a certain PQ is faster than the other PQ with respect to different input sizes.

Submission

1. Commit and push everything under the following packages to your GitHub repository:

• Main: src/main/java/edu/emory/cs/queue

• Test: test/java/edu/emory/cs/queue

2. Submit quiz2.pdf to Canvas.