Description
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.
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 removemust 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 from the first assignment apply here.
The Report
