Java PriorityQueue(堆)插入n个元素的时间复杂度？

Question

我想知道是什么的Java的时间复杂度PriorityQueue.Add()为n元素.

我理解可能更糟糕的情况下插入单个元素O(log(n)),但我不清楚插入n元素集合的时间复杂度是多少？

我已经看到来自各种来源(没有证明)的声明,即构建优先级队列堆n元素的时间O(n),并且还看到声称它是O(nlog(n)),这在插入时是有意义的O(log(n)),乘法n倍数确实相等O(nlog(n))

注意:我只对更坏的情况感兴趣,而不是摊销.

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

我没有对输入做任何假设(例如输入值集的边界或部分有序的输入).

Answer 1

看起来n个元素的插入应该是O(n log n)

Java PriorityQueue(Java Doc)

O(log n)时间用于enqueing和dequeing方法(offer,poll,remove()和add)

O(n)用于remove(Object)和contains(Object)方法

O(1)用于检索方法(查看,元素和大小)

这些时间复杂性似乎都是最糟糕的情况(维基),除了.add().您正确地质疑边界,因为Java Doc也声明了这个未绑定结构的扩展:

未指定增长政策的详细信息

正如他们在Doc中所述,PriorityQueue基于具有特定初始容量的阵列.我认为增长将花费O(n)时间,这也是最糟糕的时间复杂度.add().

要获得保证添加n个元素的O(n log n)时间,您可以声明n个元素的大小以省略容器的扩展:

PriorityQueue(int initialCapacity)

编辑: O(n)施工时间的索赔是正确的(如评论中@pjs所述).此过程通常称为heapify,适用于预先存在的数组,该数组用于在O(n)时间内在其上构建二叉树.

Answer 2

在一般情况下，它是O(N log N)。的O（N）算法存在其中输入已经订购的特殊情况下，但这不是在设置java.util.PriorityQueue。