什么是java priorityQueue poll()方法的大O.

Question

我检查了http://en.wikipedia.org/wiki/Priority_queue 它说Naive实现是o(n).

如果我使用二进制搜索,它将是log(n).但我不确定它是否在Java中使用.我如何在priorityQueue上使用二进制搜索？

谢谢.

Answer 1

来自PriorityQueue Javadoc:

实现注意事项:此实现提供了O(日志(n))的时间和入队方法dequeing( ,,offer 和 ); 和 方法的线性时间; 和恒定时间检索方法(, ,和).pollremove()addremove(Object)contains(Object)peekelementsize

优先级队列通常使用堆来实现.如果实现为排序数组,则可以在O(1)中查找和删除头,因为它始终是最后一个元素*,但是插入新元素是O(n),因为需要找到插入点(可能是在O(log(n))中使用二进制搜索完成,然后需要移动所有后面的元素以腾出空间,即O(n).

^{*假设head是最小的元素,并且数组按降序排序.}