Question

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 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's key to k and return the old key. replace Value (e, v): replace entry e's value to v and return the old value. toggle() transforms a min- to a max-priority queue or vice versa.
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 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 (), remove (e), replaceKey (e, k), and replace Value (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).

Answer 1

This is about implementing an adaptable and flexible priority queue using min- and max-heaps in Computer Science.

Step-by-step explanation:

The subject of this question is Computer Science, specifically the implementation of an adaptable and flexible priority queue (AFPQ) ADT using both min- and max-heaps.

A priority queue is an abstract data type that allows elements to be inserted and removed according to their priority. In a min-heap, the element with the smallest key is the root of the binary tree, while in a max-heap, the element with the largest key is the root. The implementation should use an extendable array to store the elements.

The AFPQ ADT should provide methods for inserting and removing elements from the priority queue, as well as modifying the key or value of an entry and toggling between min- and max-heap. The time complexities of the toggle(), remove(e), replaceKey(e, k), and replaceValue(e, v) operations should be efficient. The implementation should also include well-documented code with representative examples to demonstrate its functionality.