Java优先级队列（堆）插入n个元素的时间复杂性？

Question

我想知道Java PriorityQueue.Add()对于n元素的时间复杂度是多少

我知道在一个元素中插入潜在的更糟糕的情况是O(log(n))，但我不清楚插入一个n元素集合的时间复杂度是多少

我已经看到来自不同来源的声明（没有证据）说构建n元素的优先级队列堆的时间是O(n)，并且也看到声明是O(nlog(n))，这是有意义的，因为插入是O(log(n))，乘以n倍实际上等于O(nlog(n))

注：我只对更坏的情况感兴趣，而不是摊销

这个问题假设有一种逻辑方法来描述用n元素填充数据结构（堆）的行为，这与单独考虑nxlog(n)插入不同

我没有对输入做任何假设（例如输入值集的边界，或偏序输入）

Answer 1

似乎n个元素的插入应该是O（n logn）

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）时间内在其上构建二叉树

Answer 2

在一般情况下，它是O（nlogn）。对于输入已经排序的特殊情况，存在一个O（N）算法，但是java.util.PriorityQueue中没有提供该算法