Given the code below:
pq.offer(x);
pq.poll();
For the first line code, element x is inserted into Priority Queue pq, the time complexity of the offer is log(k), where k is the size of pq.
Then my question is, for the second line code that immediately follows the first line, what'll be the time complexity for poll() ?
After first line offer, the pq has already been sorted, so poll will simply retrieve and remove the head of queue, then I think it should be O(1), correct?
Thanks
According to the source code of PriorityQueue#poll, it seems that the operation is O(log n):
@SuppressWarnings("unchecked")
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
This is because siftDown is O(log n), due to the data within the PriorityQueue being stored as a heap.
Adding to and removing from a heap-based PQ are both O(log(N)).
This is stated clearly in the Javadoc.
PriorityQueueare not sorted. Items are inserted into a binary heap, which is an ordered, but not necessarily stored, data structure.