Please give explanation why you chose your answer so I can compare with answer I
ID: 3802708 • Letter: P
Question
Please give explanation why you chose your answer so I can compare with answer I chose to see difference if there are any. Thanks will give good feedback
Question 4 1 pts 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: O(1) Extract-Max: O(n) Change Priority: O(1) O nsert: O(log n) Extract-Max: O(log n) Change-Priority: O(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
ans is c
insert O(log n)
extract O(log n)
change priotity O(log n)
Priority queues are implemented using a heap. If implemented as a sorted array, inserting new elements which could be done in O(log(n)) using a binary search method