6.We have seen that if priority queues are implemented with heaps, both Insert a
ID: 3871023 • Letter: 6
Question
6.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.
Explanation / Answer
a) YES
b) This can be achieved by caching the highest priority element after every insertion or deletion. If highest priority element is cached then it can be extracted i.e. ExtractMax will be done in O(1). You might be thinking that this will increase the cost of insertion, but if you think every time an element is inserted into the queue it has to be compared only to the highest priority element , if it has more priority than the highest priority element then new element is cached otherwise just insert this after highest priority element. Thus insertion also takes constant time and both the operation have achieved O(1) complexity.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.