Java PriorityQueue（堆）插入n个元素的时间复杂度？
Time Complexity of Java PriorityQueue (heap) insertion of n elements?
我想知道 Java PriorityQueue.Add() 的时间复杂度对于 n 元素是多少。
我知道插入单个元素的潜在更坏情况是 O(log(n))，但我不清楚插入 n 元素集合的时间复杂度是多少？
我从各种来源（没有证据）看到了构建 n 个元素的优先级队列堆的时间是 O(n)，并且还看到了它的说法O(nlog(n))，这是有意义的，因为插入是 O(log(n))，它乘以 n 次确实等于 O(nlog(n))
注意：我只对最坏的情况感兴趣，而不是摊销。
这个问题假设有一种合乎逻辑的方式来描述用 n 元素填充数据结构（堆）的行为，这不同于简单地考虑 n x log(n)单独插入。
我没有对输入做出任何假设（例如输入值集的界限，或部分排序的输入）。
好像n个元素的插入应该是O(n log n)
Java 优先队列 (Java Doc)
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)
这些时间复杂度似乎都是最坏的情况 (wiki)，除了 .add()。您质疑边界是正确的，因为 Java 文档还说明了此未绑定结构的扩展：
The details of the growth policy are not specified
正如他们在文档中所述，PriorityQueue 基于具有特定初始容量的数组。我假设增长将花费 O(n) 时间，这也是 .add().
的最坏情况时间复杂度
要确保添加 n 个元素的 O(n log n) 时间，您可以声明 n 个元素的大小以忽略容器的扩展：
PriorityQueue(int initialCapacity)
编辑：
对于 O(n) 构造时间的声明是正确的（如@pjs 在评论中所述）。此过程通常称为 heapify 并在一个预先存在的数组上工作，该数组用于在 O(n) 时间内在其上构建二叉树。
一般情况下是O(N log N)。 O(N) 算法存在于输入已排序的特殊情况下，但 java.util.PriorityQueue.
中未提供
我想知道 Java PriorityQueue.Add() 的时间复杂度对于 n 元素是多少。
我知道插入单个元素的潜在更坏情况是 O(log(n))，但我不清楚插入 n 元素集合的时间复杂度是多少？
我从各种来源（没有证据）看到了构建 n 个元素的优先级队列堆的时间是 O(n)，并且还看到了它的说法O(nlog(n))，这是有意义的，因为插入是 O(log(n))，它乘以 n 次确实等于 O(nlog(n))
注意：我只对最坏的情况感兴趣，而不是摊销。
这个问题假设有一种合乎逻辑的方式来描述用 n 元素填充数据结构（堆）的行为，这不同于简单地考虑 n x log(n)单独插入。
我没有对输入做出任何假设（例如输入值集的界限，或部分排序的输入）。
好像n个元素的插入应该是O(n log n)
Java 优先队列 (Java Doc)
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)
这些时间复杂度似乎都是最坏的情况 (wiki)，除了 .add()。您质疑边界是正确的，因为 Java 文档还说明了此未绑定结构的扩展：
The details of the growth policy are not specified
正如他们在文档中所述，PriorityQueue 基于具有特定初始容量的数组。我假设增长将花费 O(n) 时间，这也是 .add().
要确保添加 n 个元素的 O(n log n) 时间，您可以声明 n 个元素的大小以忽略容器的扩展：
PriorityQueue(int initialCapacity)
编辑： 对于 O(n) 构造时间的声明是正确的（如@pjs 在评论中所述）。此过程通常称为 heapify 并在一个预先存在的数组上工作，该数组用于在 O(n) 时间内在其上构建二叉树。
一般情况下是O(N log N)。 O(N) 算法存在于输入已排序的特殊情况下，但 java.util.PriorityQueue.