Recall the Priority Queue ADT allows for the following operations: Insert. Extra
ID: 3863144 • Letter: R
Question
Recall the Priority Queue ADT allows for the following operations: Insert. Extract-Max. Change-Priority. Suppose we implement a priority queue using a hash table, where Insert(priority./identifier) has the effect of adding the pair (identifier. priority). using identifier as the value to be hashed. 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 on expected running time that apply. Insert: O(n) Extract-Max: O(1) Change-Priority: O(1) Insert: 0(1) Extract-Max: O(n) Change-Priority: O(1) Insert: O(log n) Extract-Max: O(log n) Change-Priority: 0(log n) Insert: O(n) Extract-Max: O(1) Change-Priority: O(n) Insert: O(1) Extract-Max: O(1) Change-Priority: O(1)Explanation / Answer
E)
Insert: O(1)
Extract-Max:O(1)
Change-Priority:O(1)
Insert, extract-max and change priority all the three have O(1) complexity or running time.In computer science, a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.