从集合构造PriorityQueue的时间复杂度是多少？ [英] What is the time complexity of constructing a PriorityQueue from a collection?

问题描述

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

What is the complexity of Java's PriorityQueue constructor with a Collection? I used the constructor:

PriorityQueue(Collection<? extends E> c)

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

Is the complexity O(n) or O(n*log(n))?

推荐答案

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

The time complexity to initialize a PriorityQueue from a collection, even an unsorted one, is O(n). Internally this uses a procedure called siftDown() to "heapify" an array in-place. (This is also called pushdown in the literature.)

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

This is counterintuitive. It seems like inserting an element into a heap is O(log n) so inserting n elements results in O(n log n) complexity. This is true if you insert the elements one at a time. (Internally, inserting an individual element does this using siftUp().)

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

Heapifying an individual element is certainly O(log n), but the "trick" of siftDown() is that as each element is processed, the number of elements that it has to be sifted past is continually decreasing. So the total complexity isn't n elements times log(n); it's the sum of n terms of the decreasing cost of sifting past the remaining elements.

请参见此答案，另请参见本文可以通过数学计算。

See this answer, and see also this article that works through the math.

这篇关于从集合构造PriorityQueue的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！