在带有`java.util.PriorityQueue`的`initialCapacity=n`中插入‘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循环的时间复杂度(大-O表示法)。

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

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

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

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

PS:我已经看过这了，但是对这个问题的回答只是声称一些没有解释的东西，而且可能它们并不是那么具体。

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

Answer 1

我理解PriorityQueue没有指定底层数据结构增长的细节。

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

(在最坏的情况下，当扩展内部数组并在新分配的空间上复制所有元素时，它可能是O(n) )。

目前的策略(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时。

假设当我指定initialCapacity并且不添加超过这个“初始化容量”的元素时，那么上述循环的最坏情况时间复杂度应该是O(n)而不是O(nlog(n))。我从这里了解到堆的建造时间是O(n)，nlog(n)是一个松散的上限。 我是对的，还是遗漏了什么？

我觉得你漏掉了什么。

假设输入数组未排序，则构建堆(“堆化”)并按顺序检索元素相当于按优先级顺序排序元素。这是一个平均O(nlogn)操作。虽然堆化本身是O(n) (因为代码使用sift向下堆化)，但实际上已经将一些排序成本推迟到以后。

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

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

由于上述原因，总的复杂性(添加和删除n个元素)将是O(nlogn)。

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

如果集合未排序，则必须对元素进行索引；请参阅上文。有一些特殊的代码来处理跳过堆化步骤的SortedCollection。

备注：

1. 您可以通过读取PriorityQueue的源代码来确认上面的详细信息。谷歌可以帮你找到它。
2. HeapSort上的维基百科页面谈论堆化
3. 基于数组的数据结构加倍增长的证明是每插入O(1)，这在好的算法教科书中给出了。同样的分析也适用于50%的生长。
4. 您的lambda表达式(a, b) -> b - a对于排序整数是不正确的，除非它们是正的。