Please give explanation why you chose your answer so I can compare with answer I
ID: 3802685 • 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 6 1 pts Suppose we wish to use a priority queue inside another algorithm, where we know there will be n Insert operations, m2 Change-Key operations, and n Extract-Max operations. Which data structure should we use to implement the priority queue in order to minimize the asymptotic expected running time? Binary heap, as seen in class Sorted list (as 1 question above) Hash table (as two questions above) O Question 7 1 pts 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(r) Insert: O(1) Extract-Max: O(1) Insert: O(r) Extract-Max: O(r)Explanation / Answer
Q6) Binary Heap
we can implement priority queue with LinkedList and heap as it is just like the abstracted data types list and arrays
but compared to all other implimentations Heap implementation is most suitable because Priority queues can be efficiently implemented using Binary Heap(all implementation happens in binary tree) because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time. Binomoial Heap and Fibonacci Heap are variations of Binary Heap. These variations perform union also in O(logn) time which is a O(n) operation in Binary Heap.
Q7)Insertion:O(1)
Extract-Max:O(r)
one can keep all the elements in an unsorted list. Whenever the highest-priority element is requested, search through all elements for the one with the highest priority.