We have seen that if priority queues are implemented with heaps, both Insert and ExtractMax take O(log n) time. Is it possible to find some other way of implementing a priority queue so that both Insert and ExtractMax can be done in O(1) time? (Note that the question is not asking whether this is possible using heaps, but whether this is possible in any way, maybe using heaps or maybe in some other way).

Hint: Think about the following. Consider the following algorithm to sort an array A[1..n] using priority queues:

for i <- 1 to n

Insert A[i] into the Priority Queue

for i <- n to 1

A[i] <- ExtractMax (Priority Queue)

Think about how fast this algorithm will be if both the priority queue operations can be done in O(1) time.

(a) Is it possible to do both the priority queue operations in O(1) time? Give a YES/NO answer.

(b) Explain your answer. If you have said YES, show how this can be done. If you have said NO, show how no algorithm can do this.