如何构建堆是O(N)时间复杂度？

Question

如何构建堆是O(N)时间复杂度？有人能帮助解释如何构建堆是O(N)复杂性吗？将项插入堆是O(log n)，插入重复n/2次(剩余的是叶子，不能违反堆属性)。因此，这意味着复杂性应该是O(n log n)我想。换句话说，对于我们“堆化”的每一项，到目前为止，对于堆(这是logn级)，它可能必须对每个级别过滤一次。我遗漏了什么？

Answer 1

你的分析是正确的。然而，它并不紧。

要解释为什么构建堆是一种线性操作并不容易，最好读一读。

A 大分析可以看到的算法这里.

---

主要的想法是在build_heap算法实际heapify成本不是O(log n)所有元素。

什么时候heapify调用时，运行时间取决于在进程终止之前元素在树中向下移动的距离。换句话说，它取决于堆中元素的高度。在最坏的情况下，元素可能会一直下降到叶级。

让我们逐级计算所做的工作。

在最底层，2^(h)节点，但我们不调用heapify所有这些，所以工作是0。在水平的旁边有2^(h − 1)节点，每个节点可能向下移动一个级别。在第三层，从底部，有2^(h − 2)节点，每个节点可能向下移动2个级别。

如您所见，并非所有堆化操作都是O(log n)，这就是为什么你要O(n).