从集合构建PriorityQueue的时间复杂度是多少？

Java的PriorityQueue构造函数的复杂性是Collection多少？我用了构造函数:

PriorityQueue(Collection c)

复杂度是O(n)还是O(n*log(n))？

PriorityQueue从集合（甚至是未排序的集合）初始化a的时间复杂度为O（n）。在内部，它使用称为siftDown()“就地”堆化数组的过程。（这在文献中也称为下推式）。

这是违反直觉的。似乎将一个元素插入到堆中是O（log n），所以插入n个元素会导致O（n log n）的复杂性。如果您一次插入一个元素，则为true。（在内部，插入单个元素使用来完成siftUp()。）

堆放单个元素肯定是O（log n），但是“窍门” siftDown()是，随着每个元素的处理，必须筛选通过的元素数量不断减少。因此，总复杂度不是n个元素乘以log（n）；它是筛选剩余元素的成本降低的n个项的总和。

请参阅此答案，还请参阅本文，通过数学工作。