A priority Queue has the following two basic operations: Insert a new item Remove the item...

Transcribed Image Text:

A priority Queue has the following two basic operations: Insert a new item Remove the item with the largest key. (This also includes FINDING the max.) We considered several underlying implementations of the priority queue each with widely varying performance characteristics. Complete the following table using O(1), O(lg N), O(N), O(N Ig N), or O(N) to denote the complexity of each operation using the given implementation strategy on the left. Please assume the array will not need a resize operation during an insert or remove for this exercise and that list implies a singly list with head and tail pointers. Unordered Array Unordered List Ordered Array Ordered List Heap Insert Remove Maximum 2) (10 points) (A.) Describe an algorithm for removing the maximum from a priority queue implemented as an unordered list. (B.) Describe an algorithm for inserting a new key value into a priority queue implemented as an ordered array. A priority Queue has the following two basic operations: Insert a new item Remove the item with the largest key. (This also includes FINDING the max.) We considered several underlying implementations of the priority queue each with widely varying performance characteristics. Complete the following table using O(1), O(lg N), O(N), O(N Ig N), or O(N) to denote the complexity of each operation using the given implementation strategy on the left. Please assume the array will not need a resize operation during an insert or remove for this exercise and that list implies a singly list with head and tail pointers. Unordered Array Unordered List Ordered Array Ordered List Heap Insert Remove Maximum 2) (10 points) (A.) Describe an algorithm for removing the maximum from a priority queue implemented as an unordered list. (B.) Describe an algorithm for inserting a new key value into a priority queue implemented as an ordered array.

Answer rating: 100% (QA)

The complexities are as follows Unordered Array Its a priority queue So the element with highest priority will be in the first placeIt is unordered so ... View the full answer