时间戳

首页 > 解决方案 > 堆数据结构的复杂性

data-structures - 堆数据结构的复杂性

问题描述

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

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) 时间可以通过解决以下问题来证明：

在此处输入图像描述 图片由 HostMath 提供

我在这里所理解的 O(h) 意味着每个节点的 heapify 的最坏情况，所以如果节点在根中，heap=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 所以根是 {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.growthwiththeweb.com/data-structures/binary-heap/build-heap-proof/ 这是我使用的参考资料，我也在 CLRS 书中读到了这个

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

标签： data-structurestime-complexitybinary-treebig-oheap

解决方案

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

对于 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 swaps 才能被 heapified。（这里最多1个节点，即根）

所以，总和可以写成：

(1 xn/2 + 2 xn/4 + 3 xn/8 + ... + log nxn/2^logn)

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

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

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

推荐阅读