优先队列 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 中的数据被存储为堆。

Answer 2

添加到基于堆的 PQ 和从中删除都是 O(log(N)).

这在 Javadoc 中有明确说明。

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

Priority Queue poll() time complexity

java

queue

big-o

priority-queue

time-complexity