Java PriorityQueue（堆）插入 n 个元素的时间复杂度？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/47420638/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Time Complexity of Java PriorityQueue (heap) insertion of n elements?
提问by James Wierzba
I would like to know what the time complexity of Java PriorityQueue.Add()is for nelements.
我想知道 JavaPriorityQueue.Add()对n元素的时间复杂度是多少。
I understand that potential worse case insertion a single element is O(log(n)), but it is not clear to me what the time complexity is for inserting a collection of nelements?
我知道插入单个元素的潜在更坏情况是O(log(n))，但我不清楚插入n元素集合的时间复杂度是多少？
I've seen claims from various sources (with no proofs) that the time to build a priority queue heap of nelements it is O(n), and have also seen claims that it is O(nlog(n)), which makes sense given insertion is O(log(n)), which multiplied ntimes would indeed equal O(nlog(n))
我已经看到来自各种来源（没有证据）的声明，即构建n元素的优先队列堆的时间是O(n)，并且还看到声明是O(nlog(n))，这是有道理的，给定插入是O(log(n))，乘以n时间确实等于O(nlog(n))
Note: I'm only interested in worse case, not amortized.
注意：我只对更坏的情况感兴趣，而不是摊销。
This question assumes there is a logical way to describe the act of populating a data structure (heap) with nelements, that is different than simply considering nx log(n)insertions individually.
这个问题假设有一种逻辑方式来描述用n元素填充数据结构（堆）的行为，这与单独考虑nx 次log(n)插入不同。
I'm making no assumptions regarding the input (such as a bounds on the set of input values, or a partially ordered input).
我对输入不做任何假设（例如输入值集的界限，或部分排序的输入）。
采纳答案by user207421
It is O(N log N)in the general case. An O(N)algorithm exists for the special case where the input is already ordered, but this isn't provided in java.util.PriorityQueue.
在一般情况下，它是O(N log N)。的O（N）算法存在其中输入已经订购的特殊情况下，但这不是在设置java.util.PriorityQueue。
回答by gue
It seems like the insertion of n elements should be O(n log n)
似乎 n 个元素的插入应该是 O(n log n)
Java PriorityQueue(Java Doc)
Java PriorityQueue（Java 文档）
O(log n) time for the enqueing and dequeing methods (offer, poll, remove() and add)
O(n) for the remove(Object) and contains(Object) methods
O(1) for the retrieval methods (peek, element, and size)
入队和出队方法（offer、poll、remove() 和 add）的 O(log n) 时间
用于 remove(Object) 和 contains(Object) 方法的 O(n)
O(1) 用于检索方法（peek、element 和 size）
These time complexities seem all worst case (wiki), except for .add(). You are right to question the bounds as the Java Doc also states to the extension of this unbound structure:
这些时间复杂性似乎都是最坏的情况 ( wiki)，除了.add(). 您质疑边界是正确的，因为 Java Doc 还说明了此未绑定结构的扩展：
The details of the growth policy are not specified
增长政策细节不详
As they state in the Doc as well, the PriorityQueue is based on an array with a specific initial capacity. I would assume that the growth will cost O(n) time, which then would also be the worst case time complexity for .add().
正如他们在 Doc 中所述，PriorityQueue 基于具有特定初始容量的数组。我假设增长将花费 O(n) 时间，这也是.add().
To get a guaranteed O(n log n) time for adding n elements you may state the size of your n elements to omit extension of the container:
为了保证 O(n log n) 时间添加 n 个元素，您可以声明 n 个元素的大小以省略容器的扩展：
PriorityQueue(int initialCapacity)
EDIT:To the claim of O(n) time for construction is correct (as stated by @pjs in the comments). This procedure is often called heapifyand works on an pre existing array that is used to construct a binary tree on it in O(n) time.
编辑：声称 O(n) 构造时间是正确的（如@pjs 在评论中所述）。这个过程通常被称为heapify并在预先存在的数组上工作，该数组用于在 O(n) 时间内在其上构建二叉树。
