java - 在 `n` 和 `java.util.PriorityQueue` 中插入 `initialCapacity=n` 元素的时间复杂度

Question

我必须从一个数组(在下面的代码中称为 nums)构造一个最大堆，所以我使用 java.util.PriorityQueue。

我的代码是这样的:

PriorityQueue<Integer> pq = new PriorityQueue<>(nums.length, (a, b) -> b - a);
for (int i = 0; i < nums.length; i++) {
    pq.offer(nums[i]);
}

我正在尝试找出上述 for 循环的时间复杂度(根据 Big-O 表示法)。

据我所知，PriorityQueue 没有指定底层数据结构增长的细节。 (在最坏的情况下，当扩展内部数组并将所有元素复制到新分配的空间时，它可能是 O(n)。

但我假设当我指定 initialCapacity 并且不添加超过此 initialCapacity 的元素时，上述循环的最坏情况时间复杂度应该是 O(n) 而不是 O(nlog(n))。我从here了解到堆的构建时间是 O(n) 并且 nlog(n) 是一个宽松的上限。

我是否正确，还是我遗漏了什么？

我只想了解，如果我使用 n 的 initialCapacity 配置我的 PriorityQueue 并添加 n 元素在那个优先级队列中，这个构建堆过程的时间复杂度是多少？

PS:我已经看到了this ，但是这个问题的答案只是在没有解释的情况下声明了一些东西，而且它们可能不是特定于 Java 的。

我还看到 java.util.PriorityQueue 有一个接受 Collection 的构造函数。这个构造函数的时间复杂度是多少？不应该是O(n)吗？

Answer 1

I understand that PriorityQueue don't specify the details of the growth of underlying data structure.

让我们弄清楚这一点。 javadoc 声明未指定扩展队列的策略。

(And in worst-case it can be O(n) when expanding the internal-array and copying all the elements over the newly allocated space).

当前的政策(Java 11)是:

    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));

对于“双重”政策，每次插入的摊销成本为 O(1)。对于增长 50% 来说并不是那么好。但它比 O(n) 好得多。

可以肯定地说，无论当前规范(技术上)允许什么，他们都不会单方面将此政策更改为更复杂的政策。

但是，这与您的问题无关，因为您正在使用 initialCapacity 容量，无论是明确地，还是当您填充 PriorityQueue 时一个集合。

I assume that when I specify the initialCapacity and don't add elements more than this `initialCapacity, then the worst case time complexity of the above loop should be O(n) instead of O(nlog(n)). I understand from here that building time of heap is O(n) and nlog(n) is a loose upper bound.

Am I correct, or am I missing something?

我觉得你漏掉了什么。

假设您的输入数组未排序，构建堆(“heapification”)并按顺序检索元素等同于按优先顺序对元素进行排序。这平均是一个 O(nlogn) 操作。虽然堆化本身是 O(n)(因为代码使用筛选堆化)，但实际上您已经推迟了一些排序成本。

因此，除非您只想检索放入队列的元素的非 O(n) 子集，否则总体答案是 O(nlogn)。

I just want to understand that if I configure my PriorityQueue with initialCapacity of n and add n elements in that priority-queue, what will be the time complexity of this building-heap process?

由于上述原因，整体复杂度(添加和删除 n 个元素)将为 O(nlogn)。

I also see that PriorityQueue has a constructor that takes in a Collection. What will be the time complexity of this constructor? Shouldn't it be O(n)?

如果集合是未排序的，那么元素必须堆化；往上看。有一些特殊情况代码可以处理跳过堆化步骤的 SortedCollection。

---

注意事项:

1. 您可以通过阅读PriorityQueue 的源代码来确认上述详细信息。 Google 可以为您找到它。
2. HeapSort 上的维基百科页面谈堆化
3. 优秀的算法教科书中给出了通过将基于数组的数据结构加倍来实现每次插入的 O(1) 增长的证明。同样的分析可以应用于增长 50%。
4. 您的 lambda 表达式 (a, b) -> b - a 对整数排序不正确，除非它们是正数。