PriorityQueue addAll() 的复杂度

Question

PriorityQueue的addAll方法的时间复杂度是什么？它是逐个添加元素导致O(n log n)，还是使用构建堆的过程在O(n)的时间内将无序元素创建成一个堆？

- user1908488

Answer 1

Javadoc似乎暗示addAll是从AbstractQueue继承而来的，在那里它被实现为一系列添加操作。

这使我相信复杂度为O(mlogn)，其中m是插入的集合大小。

- Karthik T

---

...? _O(m log n)_，而不是 _O(m n log n)_。 - Louis Wasserman

我认为这应该是 O(m log(n+m))。考虑当 n=0 时的情况。 - Sean L

Answer 2

来自优先级队列

...这个实现为入队和出队方法提供了 O(log(n)) 的时间复杂度...

所以你只能假设 n log(n)。

然而，显然，这只是你可以假设的。根据你计划使用的具体实现，你可能会发现一些技巧，可以改善问题。

- OldCurmudgeon

Answer 3

看起来，在OpenJDK中，PriorityQueue继承了addAll的实现方式，该方式从AbstractQueue中迭代集合并在每个元素上调用add方法。

来源

- HiJon89

Answer 4

PriorityQueue 中的 addAll 方法为每个元素实现了 add 方法。 因此，它的时间复杂度为 nlogn。

但这并不意味着没有类似于 Python 的 heapq.heapify() 或 C++ 的 make_heap 方法可以在 O(n) 复杂度下运行。 PriorityQueue 有一个构造函数，可以使用 O(n) 复杂度执行堆化操作。

List<Integer> x = Arrays.asList(1, 54, 22, 87, 242, 32, 11, 90);
PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>(x); // O(n) complexity

PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>();
pq2.addAll(x); // nlogn complexity

- Aman Prakash

---

是的，但它使用自然排序（因此对于Ints来说是最小堆）。有没有办法使用自定义比较器运行heapify呢？ - undefined