CS310 Priority Queue ADT Phase 3

The Program:

For this assignment, you will write one more implementations of a Priority Queue . Using the same interface as program #1, you will write a binary heap implementation. Additionally, you will write a report (details follow).

Your heap implementation must have identical behavior, and must implement the PriorityQueue interface used in program #1. The implementation must have two constructors as in the first assignment--use the DEFAULT_MAX_CAPACITY in the interface for one constructor and take a size parameter for the second.

Thus, your project will consist of the following files. You must use exactly these filenames.

• PriorityQueue.java The ADT interface (provided in prog1)
• BinaryHeapPriorityQueue.java The binary heap implementation.

Additional Details:

• Each method must be as efficient as possible. That is, a O(n) is unacceptable if the method could be written with O(log n) complexity. Both insert and remove must be O(log n)
• Your BinaryHeap must be stable--able to determine the oldest entry among those with identical priority.
• Your iterator must be fail-fast.
• You may not make any modifications to the PriorityQueue interface provided. I will grade your project with my copy of this file. This interface is UNCHANGED from projects #1 and #2
• All relevant requirements fro m the first assignment apply here.

The Report

You will provide complexity analysis for the insert(E obj) and remove() methods in all five implementations (10 methods total). You will also run empirical timing tests on all five of your implementations to provide evidence that your two methods perform at the expected complexity. You should graph the runtime results from the 10 methods and provide written justification for you results. Attach your report to your Binary Heap source code to make a single submission package; do not give me two items.