Java Priority Queue Interface Implementation

Question

This were the questions I was asked in the interview fews days back and I was not sure about the approach. Suggestions would be highly appreciated:

How can I have implement PriorityQueue interface to get queue() method in O(1) and dequeue() method in O(n).

How can I have implement PriorityQueue interface to get queue() method in O(n) and dequeue() method in O(1).

Thanks.

Answer 1

A typical PriorityQueue implementation would use a Heap to get O(lg n) performance for the "add" operation, so O(n) performance will be even easier.

For example, you could use a vector or linked list as the underlying data structure. For O(1) "add" you can simply add the new value to the end and for O(n) "remove" you can do a linear search for the min value. Conversely, for O(n) "add" you can do a linear scan to find the next largest value then insert before it, for O(1) remove you can simply remove the first element of the list.