In class, we discussed the priority queue $($PQ$)$ ADT implemented using min$-$heap. In a min$-$heap, the element of the heap with the smallest key is the root of the binary tree. On the other hand, a max$-$heap has as root the element with the biggest key, and the relationship between the keys of a node and its parent is reversed of that of a min$-$heap. We also discussed an array$-$based implementation of heaps.

In this programming assignment, your task is to implement your own adaptable and flexible priority queue $($AFPQ$)$ ADT using both min$-$ and max$-$heap. The specifications of the AFPQ are provided in the following. the heap$($s$)$ must be implemented from scratch using an array that is dynamically extendable. You are not allowed to use any list $($including arraylist$),$ tree, vector, or heap implementation already available in Java. You must not duplicate code for implementing min$-$ and max$-$heaps $($i$.$e$.$ the same code must be used for constructing min or max heaps. Hence think of a flexible way to parameterize your code for either min$-$ or max heap$).$

The priority queue is also adaptable meaning that any key or value of any entry of the priority queue can be modified, where the entry object is passed as a parameter. An entry can also be removed from anywhere in the priority queue. The following are the access methods of the AFPQ ADT:

removeTop$()$: removes and returns the entry object $($a key, value pair$)$ with the smallest or biggest key depending on the current state of the priority queue $($either Min or Max$).$

insert $($ k$,$v $)$: Insert $($ k$,$v $)$ which is a key$($k$),$ value$($v$)$ pair to the priority queue, and returns the corresponding entry object in the priority queue.

top$()$: returns the top entry $($with the minimum or the maximum key depending on whether it is a Min$-$ or Max$-$priority queue, without removing the entry.

remove $($e$)$: Removes entry object e from the priority queue and returns the entry

replaceKey $($ e$,$k $)$: replace entry e$\text{'}$s key to k and return the old key.

replaceValue $($ e$,$v$)$ : replace entry e$\text{'}$s value to v and return the old value.

toggle$()$ transforms a min$-$ to a max$-$priority queue or vice versa.

state $0$ : returns the current state $($Min or Max$)$ of the priority queue.

isEmpty$)$: returns true if the priority queue is empty.

size $(0$: returns the current number of entries in the priority queue

You have to submit the following deliverables:

a$)$ Pseudo code of your implementation of the AFPQ ADT using a parameterized heap that is implemented using extendable array. Note that Java code will not be considered as pseudo code. Your pseudo code must be on a higher and more abstract level.

b$)$ Tight big$-$Oh time complexities of toggle $0,$ remove $($e$),$ replaceKey $($e$,$ k $),$ and replaceValue $($e$,$v$)$ operations, together with your explanations. These methods should be as efficient as possible.

c$)$ Well documented Java source code with $20$ different but representative examples demonstrating the functionality of your implemented ADT. These examples should demonstrate all cases of your ADT functionality $($e$.$g$.,$ all operations of your ADT, several cases requiring automatic array extension, sufficient number of down and up$-$heap operations,

changing keys, and removing entries from anywhere of heap$).$