4. Heaps

• You will implement the following UML in Java:

4.1. Priority Queue

1. Create the generic class OPriorityQueue.

   • The generic type should extends Comparable.

   • OPriorityQueue extends the Java API class AbstractQueue.

   • It also implements the Java API interface Queue.

2. Implement the attribute and the methods of the class:

   • boolean offer(E item): Inserts an item into the queue. Returns true if successful; return false if the item could not be inserted.

   • E remove(E item): Removes the smallest entry and returns it if the queue is not empty. If the queue is empty, throws a NoSuchElementException.

   • E poll(E item): Removes the smallest entry and returns it if the queue is not empty. If the queue is empty, returns a null.

   • E peek(E item): Returns the smallest entry without removing it. If the queue is empty, returns a null.

   • E element(E item): Returns the smallest entry without removing it. If the queue is empty, throws a NoSuchElementException.

4.2. Breadth-First Traversal

1. Implement the following algorithm:

void breadth_first_search(OPriorityQueue queue, BinarySearchTree bst){
    Insert root node in queue;
    while(queue not empty){
        node = remove node from queue;
        visit(node);
        insert node.left in queue;
        insert node.right in queue;
    }

2. Test it on several binary trees.

ENSURE WE HAVE RECORDED YOUR COMPLETION. FAILURE TO DO SO WILL RESULT IN A GRADE OF 0!