---
description: 'Quiz 2: Priority Queues'
---

# 2.5. Quiz

## Coding

* Create a class called [`TernaryHeapQuiz`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/queue/TernaryHeapQuiz.java) under the main [`queue`](https://github.com/emory-courses/dsa-java/tree/master/src/main/java/edu/emory/cs/queue) package that extends the abstract class [`AbstractPriorityQueue`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/queue/AbstractPriorityQueue.java).
* 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()`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/queue/TernaryHeapQuiz.java#L38), [`remove()`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/queue/TernaryHeapQuiz.java#L43), and [`size()`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/queue/TernaryHeapQuiz.java#L49), such that both `add()` and `remove()` give $$O(log_3 n)$$.
* Feel free to use the code in [`BinaryHeap`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/queue/BinaryHeap.java).

## Testing

* Create the [`TernaryHeapQuizTest`](https://github.com/emory-courses/dsa-java/blob/master/src/test/java/edu/emory/cs/queue/TernaryHeapQuizTest.java) class under the test [`queue`](https://github.com/emory-courses/dsa-java/blob/master/src/test/java/edu/emory/cs/queue) package.
* Test the correctness of your `TernaryHeapQuiz` using the [`testRobustness()`](https://github.com/emory-courses/dsa-java/blob/master/src/test/java/edu/emory/cs/queue/TernaryHeapQuizTest.java#L26) 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()`](https://github.com/emory-courses/dsa-java/blob/master/src/test/java/edu/emory/cs/queue/TernaryHeapQuizTest.java#L36) method.
* Create a PDF file **quiz2.pdf** and write a report that includes the following:&#x20;
  * 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](https://github.com/emory-courses/dsa-java/tree/master/src/main/java/edu/emory/cs/queue)
* Test: [test/java/edu/emory/cs/queue](https://github.com/emory-courses/dsa-java/tree/master/src/test/java/edu/emory/cs/queue)

2\. Submit **quiz2.pdf** to Canvas.
