Priority Queue exercises

algorithm coursera

1.Suppose that the sequence
P R I O * R * * I * T * Y * * * Q U E * * * U * E
(where a letter means insert and an asterisk means remove the maximum) is applied to an initially empty priority queue. Give the sequence of values returned by remove the maximum operations.

E (left on pq)
R R P O T Y I I Q U E U (removed item)

2.Criticize the following idea: to implement find the maximum in constant time, why not keep track of the maximum value inserted so far, then return that value for find the maximum?

3.Provide priority queue implementations that support insert and remove the maximum, one for each of the following underlying data structures: unordered array, ordered array, unordered linked list, and ordered linked list. Give a table of the worst-case bounds for each operation for each of your four implementations from the previous exercise.

4.Is an array that is sorted in decreasing order a max-oriented heap.
Yes

11.Suppose that your application will have a huge number of insert operations, but only a few remove the maximum operations. Which priority-queue implementation do you think would be most effective: heap, unordered array, ordered array?
Unordered array. Insert is constant time.

12.Suppose that your application will have a huge number of find the maximum operations, but a relatively small number of insert and remove the maximum operations. Which priority queue implementation do you think would be most effective: heap, unordered array, ordered array?
Ordered array, finding the maximum is constant time.

14.What is the minimum number of items that must be exchanged during a remove the maximum operation in a heap of size N with no duplicate keys? Give a heap of size 15 for which the minimum is achieved. Answer the same question for two and three successive remove the maximum operations.
2

15.Design a linear-time certification algorithm to check whether an array pq[] is a min-oriented heap.