给定以下代码:
pq.offer(x);
pq.poll();
第一行代码,将元素x插入优先队列pq,offer
的时间复杂度为log(k),其中k为pq的大小。
那么我的问题是,对于紧跟在第一行之后的第二行代码,poll()
的时间复杂度是多少?
在第一行offer
之后,pq已经排序了,所以poll
会简单的获取并移除队列的头部,那么我认为应该是O(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
中的数据存储为堆。
关于java - 优先队列 poll() 时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46517400/