We discussed the priority queue (PQ) ADT implemented using min-heap. In a minheap,the element of the heap with the smallest key is the root of the binary tree. On the other hand, amax-heap has as root the element with the biggest key, and the relationship between the keys of anode and its parent is reversed of that of a min-heap. We also discussed an array-based implementation of heaps. In this assignment, your task is to implement your own flexible priority queue ADT using both min- and max-heap in Java. The specifications of the flexible priority queue are provided in the following.
The heap(s) must be implemented from scratch using an array that is automatically 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 following are the access methods of the flexible priority queue ADT: remove(): removes and returns the entry (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 the (k,v) entry which is a key(k), value(v) pair to the priority queue.
top(): returns the top entry (with the minimum or the maximum key depending on whether it is aMin- or Max-priority queue, without removing the entry.
toggle() transforms a min- to a max-priority queue or vice versa.
switchToMin(): transforms a max- to a min-priority queue; else leave unchanged.
switchToMax(): transforms a min- to a max-priority queue; else leave unchanged.
state (): returns the current state (Min or Max) of the priority queue.
isEmpty(): returns true if the priority queue is empty. size(): 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 flexible priority queue ADT using a parameterized heap that is implemented using extendable array. Note that Java code will notbe considered as pseudo code. Your pseudo code must be on a higher and more abstract level.
b) Tight big-Oh time complexities of toggle(), switchToMin(), and switchToMax() operations, together with your explanations.
c) Well documented Java source code with 20 different but representative examplesdemonstrating 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).