java - 优先队列 poll() 时间复杂度

Question

给定以下代码:

pq.offer(x);
pq.poll();

第一行代码，将元素x插入优先队列pq，offer的时间复杂度为log(k)，其中k为pq的大小。

那么我的问题是，对于紧跟在第一行之后的第二行代码，poll() 的时间复杂度是多少？

在第一行offer之后，pq已经排序了，所以poll会简单的获取并移除队列的头部，那么我认为应该是O(1 ), 正确吗？

谢谢

Answer 1

根据PriorityQueue#poll的源码, 好像操作是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;
}

这是因为 siftDown是O(log n) ，由于 PriorityQueue 中的数据存储为堆。