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.

Answer 2

For an O(1) approach to the queue() method you must keep track of the last element of your queue, so that you can easily append one more after it, regardless the size of your queue.

For an O(n) in queue() and O(1) in dequeue() you need to keep track of the first element of your queue in a variable, so that regardless the number of elements within it, you can remove the first from the list with always a single set of instructions (no iterations).

In each of both cases you just add one extra variable to your class.

Answer 3

Just take a look at:

http://www.docjar.com/html/api/java/util/PriorityQueue.java.html

Remember, all good programmers copy good code :P

I assume you have the basic understanding about data structures, list, maps, etc. If you dont, understanding how this work will not make much sense, instead go and investigate about the subject further.

Answer 4

queue() method in O(1) and dequeue() method in O(n):

Use a linked list and simply add every new entry directly to the head of the list in queue(). In dequeue() iterate the list and remove and return the entry with the highest priority.

queue() method in O(n) and dequeue() method in O(1):

Use a linked list again. But this time in queue() you iterate over the entries to put the new entry into it's priority sorted position (this is actually one step of an insertion sort). In dequeue() you can now always remove and return the first element of the list.

Answer 5

I would have said that PriorityQueue isn't an interface, it's a class, and I wouldn't implement anything that was O(n) if I could help it.