在 `initialCapacity=n` 的 `java.util.PriorityQueue` 中插入 `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没有指定底层数据结构增长的细节。（在最坏的情况下，当扩展内部数组并将所有元素复制到新分配的 space 时，它可能是 O(n)）。

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

我是对的，还是漏掉了什么？

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

PS：我已经看到了，但是这个问题的答案只是在没有解释的情况下声明了一些东西，可能它们并不是那么 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 容量，无论是明确地，还是当您从collection.

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?

我觉得你漏掉了什么。

假设您的输入数组未排序，构建堆（“堆化”）并按顺序检索元素等同于按优先顺序对元素进行排序。这平均是一个 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)?

如果collection是未排序的，那么元素必须堆化；往上看。有一些 special-case 代码可以处理跳过堆化步骤的 SortedCollection。

备注：

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

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

Time complexity of inserting `n` elements in a `java.util.PriorityQueue` with `initialCapacity=n`

java

algorithm

priority-queue

time-complexity