<分区>
我想知道 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 文档还说明了此未绑定(bind)结构的扩展:
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) 时间内在其上构建二叉树。
关于java - Java PriorityQueue(堆)插入n个元素的时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47420638/