Priority Queue poll() time complexity

user_815408 0
Viewed 3387

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

priority-queue big-o time-complexity queue java
2 Answers

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.

user_72946470

Adding to and removing from a heap-based PQ are both O(log(N)).

This is stated clearly in the Javadoc.

user_2074210
Related