Below is an interface for the maxPriorityQueue ADT (Abstract Data Type), as given in Page 24 of the Heapsort notes.

=================================================================

A very important feature of an abstract data structure is that it can be implemented in different ways. We will implement the above interface 1 in three ways.

1.) An implementation of this maxPriorityQueue in terms of the Heap structure has been thoroughly discussed in the lecture notes on Heapsort. Study the pseudo codes of the above methods, and implement them in Java 2 .

2.)Provide two more implementations of maxPriorityQueue, one with a sorted array, the other with an unsorted array. We have discussed these two implementations in a class. For example, with the initially empty unsorted array implementation, although you can insert the next item right in the first available place in ?(1) time, you have to look for the maximum element in the list in ?(n), where n is the number of elements as contained in such a list. Once you have extracted the maximum element from the list, you also have to fill this hole by moving all the elements to the right of such a maximum element one position to the left, also in ?(n). Finally, when you want to increase the value of an element, you can just do it in ?(1).

3.) In light of the above analysis for the unsorted case, make a theoretical analysis for the four operations in terms of n, the size of the maxPriorityQueue, for the sorted list implementation

4.)Practically, for n = 10, 50, 100, 200, 500, 1000, 2000, 5000, come up with a structure in each and every one of the above three implementations that can contain n elements, and fill them with a randomly generated list of n elements. Then, for the above three implementations, find out the average number of comparisons and movements 3 as involved in the three operations of maximum, maximum extraction, and key increase 4 .

public interface maxPriorityQueue //Below inserts x into this maxPriorityQueue public void insert (Comparable x); //Below returns the element of this maxPriorityQueue with the largest key. public comparable maximum; //The following method removes and returns the element of this //maxPriorityQueue with the largest key public comparable extractMaxO; //The following method increases the value of element located at // position i to the new value k, which is no smaller than its //original key value public void increaseKey (int i, Comparable k); public interface maxPriorityQueue //Below inserts x into this maxPriorityQueue public void insert (Comparable x); //Below returns the element of this maxPriorityQueue with the largest key. public comparable maximum; //The following method removes and returns the element of this //maxPriorityQueue with the largest key public comparable extractMaxO; //The following method increases the value of element located at // position i to the new value k, which is no smaller than its //original key value public void increaseKey (int i, Comparable k)