java - 从集合构造 PriorityQueue 的时间复杂度是多少？

Question

Java 的 PriorityQueue 构造函数的复杂度是Collection多少？我使用了构造函数：

PriorityQueue(Collection<? extends E> c)

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

Answer 1

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

这是违反直觉的。似乎将一个元素插入堆是 O(log n)，因此插入 n 个元素会导致 O(n log n) 复杂度。如果您一次插入一个元素，这是正确的。（在内部，插入单个元素使用siftUp().）

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

请参阅此答案，另请参阅这篇通过数学计算的文章。