Suppose we now have to implement a priority queue in a setting where we know the
ID: 3864032 • Letter: S
Question
Suppose we now have to implement a priority queue in a setting where we know the priorities always come from the set {1, ..., r}. We can consider yet another data structure: we maintain an array of r lists, where the i-th list contains all the elements currently in the priority queue that have priority i. How fast can the basic priority queue operations be implemented using this particular data structure, assuming the priority queue contains n elements? Choose the tightest upper bounds that apply. Insert: O(r) Extract-Max: O(1) Insert: O(1) Extract-Max: O(1) Insert: O(1) Extract-Max: O (r) Insert: O (r) Extract-Max: O(r)Explanation / Answer
No, C is correct
Generally insertion in queue (Enqueue) requires O(1) time, because queue works on first in first out, here also enqueue will be done in O(1) time. and if we talk about extraction i.e. dequeue operation; so in worst case condition (tightest upper bound) priority of all the elements will be same, then dequeue operation will take O(r) time to extract an element.
That is why Extract-max= O(r).