*****
Heaps
*****

*  You will implement the following UML in Java:

.. figure:: ./uml_priority_queue.drawio.png
   :align: center

|

Priority Queue
==============

1.  Create the **generic** class :code:`OPriorityQueue`.

    *  The generic type should **extends** :code:`Comparable`.
    *  :code:`OPriorityQueue` extends the Java API class :code:`AbstractQueue`.
    *  It also implements the Java API interface :code:`Queue`.

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

    *  :code:`boolean offer(E item)`:  Inserts an item into the queue.
       Returns :code:`true` if successful; return :code:`false` if the item could not be inserted.
    *  :code:`E remove(E item)`:  Removes the smallest entry and returns it if the queue is not empty. If the queue is empty, throws a :code:`NoSuchElementException`.
    *  :code:`E poll(E item)`:  Removes the smallest entry and returns it if the queue is not empty. If the queue is empty, returns a :code:`null`.
    *  :code:`E peek(E item)`:  Returns the smallest entry without removing it. If the queue is empty, returns a :code:`null`.
    *  :code:`E element(E item)`:  Returns the smallest entry without removing it. If the queue is empty, throws a :code:`NoSuchElementException`.

Breadth-First Traversal
=======================

1.  Implement the following algorithm:

.. code-block::

    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!**