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

Question

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

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

谢谢。

Answer 1

来自PriorityQueue Javadoc：

实现说明：此实现为入队和 出队方法（ 、和）提供O(log(n))时间；和 方法的线性时间；检索方法（、 和）的固定时间。offerpollremove()addremove(Object)contains(Object)peekelementsize

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

^{* 假设头部为最小元素，数组按降序排列。}