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

Question

带有 Collection 的 Java PriorityQueue 构造函数的复杂性是什么？ 我使用了构造函数:

PriorityQueue(Collection<? extends E> c)

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

Answer 1

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

这是违反直觉的。将一个元素插入堆中似乎是 O(log n)，因此插入 n 个元素会导致 O(n log n) 复杂度。如果您一次插入一个元素，就会出现这种情况。 (在内部，插入单个元素是使用 siftUp() 完成的。)

堆积单个元素当然是 O(log n)，但是 siftDown() 的“技巧”是在处理每个元素时，它必须筛选过去的元素数量正在不断减少。所以总复杂度不是 n 个元素乘以 log(n)；它是筛选剩余元素的递减成本的 n 项之和。

参见 this answer , 另见 this article这通过数学起作用。