从集合构造优先级队列的时间复杂程度是多少？

collections java priority-queue heap binary-heap

2022-09-04 08:45:25

Java 的 PriorityQueue 构造函数与？我使用了构造函数：Collection

PriorityQueue(Collection<? extends E> c)

复杂度是 O（n）还是 O（n*log（n））？

答案 1

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

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

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

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

答案 2