我想知道Java PriorityQueue.Add()的时间复杂性是n元素的时间。
我知道潜在的案例插入一个元素是O(log(n))，但是我不清楚插入n元素集合的时间复杂性是多少？
我已经看到了来自各种来源的主张（没有证据），即构建n元素的优先级队列堆的时间是O(n)，并且还看到声称它是O(nlog(n))，鉴于插入是O(log(n))，这是有意义的哪些n乘以O(nlog(n))
注意：我只对更糟糕的情况感兴趣，而不是摊销。
这个问题假设有一种逻辑方法可以描述用n元素填充数据结构（HEAP）的行为，这与仅考虑n x log(n)单独插入的情况不同。
我对输入没有任何假设（例如，输入值集的界限或部分有序的输入）。
似乎插入n元素应该是o（n log n）
Java Priorityqueue （Java Doc）
o（log n）启动和脱水方法的时间（要约，民意调查， 删除（）和添加）
o（n）的删除（对象）和包含（对象）方法
o（1）用于检索方法（窥视，元素和大小）
这些时间复杂性似乎都是最坏的情况（Wiki），除了.add()。您对界限的质疑是正确的，因为Java Doc还指出了这种未结构结构的扩展：
未指定增长政策的详细信息
正如他们在文档中所述的那样，优先级基于具有特定初始容量的数组。我认为增长将花费O（n）时间，这也将是.add()的最糟糕的时间复杂性。
要获得保证的O（n log n）添加n元素的时间，您可能会说明n个元素的大小以省略容器的扩展：
PriorityQueue(int initialCapacity)
编辑：对于O（n）施工时间的要求是正确的（如@PJ在评论中所述）。此过程通常称为hepify，并在o（n）时间上用于构造二进制树的预先现有数组。
在一般情况下，它是 o（n log n）。对于已经订购了输入的特殊情况，存在A o（n）算法，但这在java.util.PriorityQueue中没有提供。