Provide two 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).

Using this maxPriorityQueue interface: