CODEWITHSUNDEEP
javadata-structures
Rachel
Rachel

Reputation: 103397

Java Priority Queue Interface Implementation

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.

Upvotes: 2

Views: 2214

Answers (6)

unix_user
unix_user

Reputation: 309

Wikipedia has a solution for this--

http://en.wikipedia.org/wiki/Priority_queue#Naive_implementations

For O(1) insertion, add element to the current location and for dequeue in O(n) perform a search based on priority..

For O(n) insertion perform the search initially based on priority and add the element and for dequeue in O(1) just remove the element from the beginning or from 0th location...

The code in this example can help you understand more clearly.

http://www.java-forums.org/java-lang/7449-how-implement-priority-queue-java.html

In the above example, the dequeue takes O(1) and insertion takes O(n)

Upvotes: 0

user207421
user207421

Reputation: 310860

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.

Upvotes: 1

x4u
x4u

Reputation: 14077

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.

Upvotes: 2

Jose Diaz
Jose Diaz

Reputation: 5398

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.

Upvotes: 1

Luis Miguel Serrano
Luis Miguel Serrano

Reputation: 5099

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.

Upvotes: 0

maerics
maerics

Reputation: 156384

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.

Upvotes: 6

Related Questions