堆数据结构的复杂性

Question

我正在尝试计算运行在堆排序算法中构建堆的时间

BUILD-HEAP(A) 
heapsize := size(A); 
  for i := floor(heapsize/2) downto 1 
    do HEAPIFY(A, i); 
  end for 
END

为什么时间是线性的背后的基本思想是因为 heapify 的时间复杂度取决于它在堆中的位置。当节点是叶节点（至少占节点的一半）时需要 O(1) 时间，当它在根节点时需要 O(logn) 时间。

O(n) 时间可以通过解决以下问题来证明：

image by HostMath

我在这里的理解 O(h) 表示每个节点堆化的最坏情况，因此如果节点在根中，则高度=ln n 例如堆化节点 2、1、3 需要 ln_2 3 =1.5 根节点2的高度为1，所以调用HEAPIFY为ln_2 n=height = O(h)

BUILD-HEAP(A) 
heapsize := size(A); 
  for i := floor(heapsize/2) downto 1 
    do HEAPIFY(A, i); 
  end for 
END 




 suppose this is the tree

       4    .. height2
      / \ 
    2   6  .. height 1
    /\   /\  
  1 3 5 7  .. height 0

快速浏览上述算法表明运行时间为 O(nlg(n))，因为每次调用 Heapify 的成本为 O(lg(n))，而 Build-Heap 的成本为 O( n) 这样的电话。这个上限虽然正确，但不是渐近紧的。构建二叉堆的时间复杂度为 O(n)。

我试图理解，heapsize/2 意味着 for 循环只调用 HEAPIFY heapsize/2 次。在上面的树中，heapsize=7, 7/2= 3 所以 root 将是 {1,2,6} 所以 n/2

并且每次调用 HEAPIFY 都会再次调用 HEAPIFY，直到到达每个根的最后一片叶子，例如 2 会调用 heapify 1 次，6 会调用 heapify 1 次，1 会调用 heapify 2 次。所以树的高度是 ln n。我说得对吗？

那么复杂度就是 O(n/2 * ln n) = O(n ln n)

哪一个是正确的？ O(n ln n) 或 O(n)?

我怎样才能得到 O(n)？

我正在阅读此作为参考，如果我不对请指正谢谢！ https://www.growingwiththeweb.com/data-structures/binary-heap/build-heap-proof/ 这是我使用的参考，我也在 CLRS 书中读到过这个

https://www.hostmath.com/Show.aspx?Code=ln_2%203

Answer 1

复杂度为 O(n) 这就是原因。假设树有 n 个节点。由于堆是一棵几乎完整的二叉树（根据 CLRS），因此节点的后半部分都是叶子；所以，没有必要堆砌它们。现在剩下的一半。我们从位置 n/2 的节点开始并向后移动。在heapifying中，一个节点只能向下移动，所以正如你提到的，它最多需要与节点交换操作的高度一样多才能完成该节点的heapify。

对于 n 个节点，我们最多有 log n 个级别，其中级别 0 有根，级别 1 最多有 2 个节点，依此类推：

level 0:              x
.                    / \  
level 1:            x   x
.
level log n:    x x x x x x x x

所以，我们有以下内容：

logn-1级的所有节点最多需要1次交换才能堆化。（这里最多n/2个节点）

级别logn-2的所有节点最多需要2次交换才能被堆化。（这里最多n/4个节点）

.....

级别0的所有节点最多需要logn次交换才能被堆化。（这里最多1个节点，即根节点）

所以，总和可以写成：

(1 x n/2 + 2 x n/4 + 3 x n/8 + ... + log n x n/2^logn)

让我们分解出 n，我们得到：

n x (1/2 + 2/4 + 3/8 + ... + log n/2^logn)

现在总和 (1/2 + 2/4 + 3/8 + ... + log n/2^logn) 总是 <= 2（参见）；因此，我们感兴趣的上述总和总是 <= 2 x n。因此，复杂度为 O(n)。

堆数据结构的复杂性

complexity of heap data structure

heap

big-o

binary-tree

time-complexity

data-structures