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.

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.

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.

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

2. Submit quiz2.pdf to Canvas.

Last updated 2 years ago

Was this helpful?

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.

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.