有人可以帮助解释如何构建堆是O(n)复杂性？
将项插入堆中O(log n),并且插入重复n/2次(其余为叶,并且不能违反堆属性).所以,这意味着复杂性应该是O(n log n),我想.
换句话说,对于我们"堆积"的每个项目,它有可能必须针对堆的每个级别过滤一次(这是log n级别).
我错过了什么？
Java的PriorityQueue构造函数的复杂性是Collection多少？我用了构造函数:
PriorityQueue(Collection<? extends E> c)
复杂度是O(n)还是O(n*log(n))？