相关疑难解决方法(0)

有人可以帮助解释如何构建堆是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))？

在阅读了诸如为什么在 heapify 中 siftDown 比 siftUp 更好？我有印象

1. siftDown() 比 siftUp() 好
2. siftDown() 总是可以代替 siftUp() ，反之亦然

为什么很多堆结构实现都有在 insert() 上调用的 siftUp()？维基百科的文章有它。