What is big O of java priorityQueue poll() method [closed]

Question

I checked http://en.wikipedia.org/wiki/Priority_queue it said Naive implementations is o(n).

If I use binary search, it will be log(n). But I am not sure if it is used in Java. And how do I use binary search on a priorityQueue?

Thanks.

Answer 1

From the PriorityQueue Javadoc:

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

Priority queues are typically implemented using a heap. If implemented as a sorted array, the head can be looked up and removed in O(1) since it is always the last element*, but inserting new elements is O(n) since the insertion point needs to be found (which could be done in O(log(n)) using a binary search) and then all the later elements need to be shifted to make room, which is O(n).

^{* Assuming the head is the smallest element and the array is sorted in descending order.}