As you have learned in CS$1$ that heap data structure can be used to maintain a priority

queue. The run$-$time for both insertion and deletion for a single item is O$($log n$).$ In a

min heap the smallest number will be in the root of the tree and in a maxheap the

largest number will be at the root of the tree. So$,$ if you remove something from minhip,

you will get the smallest number and for a maxheap you will get the max number from

the heap.

Unlike CS$1,$ you really don$$t have to implement your own heap. Java has a PriorityQueue

class that is actually an implementation of minheap. If you want to use it for maxheap

you just need to pass Collections.reverseOrder$()$ while instantiating the

PrirityQueue.

For the most part in a priority queue you will be working with four main methods:

$$ q$.$add$($newValue$)$;

$$ q$.$poll$()$;

$$ q$.$peek$()$;

$$ q$.$size$()$;

$$ Add: The add method for a priority queue behaves in $()$ runtime. The $$ in this

runtime is the number of elements in the priority queue at the time of addition. Here

log means log base $2.$ If you plug $1,000,000$ in to the log function of your calculator,

you will see this is not a large number of steps. This makes priority queues a nice

choice for speeding up problems where you need to know either the largest or

smallest element you would like to process next.

$$ The purpose of this method is to add an element to the container. Note that the

runtime of $()$ is worse than the runtime $().$ Essentally we are paying for the

fast lookup of the smallest element by making adding elements slower. Sometimes

this is a worthy tradeoff.

$$ Poll: This method takes the smallest element in the queue based on each objects

compareTo method and removes it from the queue. The method call takes

$()$ time as well as the structure must rearrange itself to figure out the next

smallest element.

$$ Peek: This method allows you access to the smallest element in the queue without

removing it$.$ It works the same as ArrayDeque$$s peek method and even runs in $()$

time!