702

有人可以帮助解释构建堆如何成为O(n)复杂度吗？

将项目插入堆是O(log n)，并且插入重复 n/2 次（其余的是叶子，并且不能违反堆属性）。所以，这意味着复杂度应该是O(n log n)，我想。

换句话说，对于我们“堆积”的每个项目，它有可能必须为到目前为止的堆的每个级别（即log n级别）过滤（即筛选）一次。

我错过了什么？

4

16 回答 16

738

我认为这个话题中隐藏着几个问题：

  • 你如何实现buildHeap它在O(n)时间内运行？
  • 如果正确实施，你如何证明它buildHeap在O(n)时间内运行？
  • 为什么相同的逻辑不能使堆排序在O(n)而不是O(n log n ) 时间内运行？

你如何实现buildHeap它在O(n)时间内运行？

通常，这些问题的答案集中在 和 之间的区别siftUp上siftDown。siftUp在和之间做出正确选择siftDown对于获得 的O(n)性能至关重要buildHeap，但对于帮助人们理解 和 之间的区别没有任何buildHeap帮助heapSort。事实上，两者的buildHeap正确实现heapSort只会使用siftDown. 该siftUp操作只需要对现有堆执行插入操作，因此它将用于使用例如二叉堆实现优先级队列。

我写这篇文章是为了描述最大堆是如何工作的。这是通常用于堆排序或优先级队列的堆类型，其中较高的值表示较高的优先级。最小堆也很有用；例如，当检索具有按升序排列的整数键或按字母顺序排列的字符串的项目时。原理完全相同；只需切换排序顺序。

heap 属性指定二进制堆中的每个节点必须至少与其两个子节点一样大。特别是，这意味着堆中最大的项目在根。向下筛选和向上筛选本质上是相反方向的相同操作：移动一个违规节点，直到它满足堆属性：

  • siftDown将一个太小的节点与其最大的子节点交换（从而将其向下移动），直到它至少与它下面的两个节点一样大。
  • siftUp将一个太大的节点与其父节点交换（从而将其向上移动），直到它不大于它上面的节点。

所需的操作数量siftDown与siftUp节点可能必须移动的距离成正比。对于siftDown，它是到树底部的距离，因此siftDown对于树顶部的节点来说是昂贵的。使用siftUp时，工作与到树顶的距离成正比，因此siftUp对于树底的节点来说是昂贵的。尽管在最坏的情况下这两个操作都是O(log n)，但在堆中，只有一个节点位于顶部，而一半节点位于底层。因此，如果我们必须对每个节点应用一个操作，我们会更siftDown喜欢siftUp.

该buildHeap函数获取一个未排序项的数组并移动它们，直到它们都满足堆属性，从而产生一个有效的堆。有两种方法可以buildHeap使用我们描述的siftUpand操作。siftDown

  1. 从堆的顶部（数组的开头）开始并调用siftUp每个项目。在每一步，先前筛选的项目（数组中当前项目之前的项目）形成一个有效的堆，并且向上筛选下一个项目将其放置到堆中的有效位置。筛选完每个节点后，所有项目都满足堆属性。

  2. 或者，朝相反的方向走：从阵列的末端开始，向后移动到前面。在每次迭代中，您都会向下筛选一个项目，直到它位于正确的位置。

哪种实现buildHeap更有效？

这两种解决方案都会产生一个有效的堆。毫不奇怪，更有效的是使用siftDown.

令h = log n表示堆的高度。该siftDown方法所需的工作由总和给出

(0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).

总和中的每一项都具有给定高度处的节点必须移动的最大距离（底层为零，根为 h）乘以该高度处的节点数。相反，siftUp在每个节点上调用的总和是

(h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).

应该清楚的是，第二个总和更大。单独的第一项是hn/2 = 1/2 n log n，因此这种方法最多具有复杂性O(n log n)。

我们如何证明该siftDown方法的总和确实是O(n)？

一种方法（还有其他分析也有效）是将有限和转换为无限级数，然后使用泰勒级数。我们可以忽略第一项，它是零：

构建堆复杂度的泰勒级数

如果您不确定为什么每个步骤都有效，以下是该过程的理由：

  • 这些项都是正数，因此有限和必须小于无限和。
  • 该系列等于在x=1/2处评估的幂级数。
  • 该幂级数等于（常数乘以）泰勒级数对f(x)=1/(1-x)的导数。
  • x=1/2在该泰勒级数的收敛区间内。
  • 因此，我们可以将泰勒级数替换为1/(1-x)，进行微分和求值以找到无穷级数的值。

由于无限和恰好是n，因此我们得出结论，有限和不会更大，因此是O(n)。

为什么堆排序需要O(n log n)时间？

如果可以buildHeap在线性时间内运行，为什么堆排序需要O(n log n)时间？好吧，堆排序由两个阶段组成。首先，我们调用数组，如果实现最佳buildHeap，则需要O(n)时间。下一阶段是重复删除堆中最大的项并将其放在数组的末尾。因为我们从堆中删除了一个项目，所以在堆的末尾总是有一个空位可以存储该项目。所以堆排序是通过依次取出下一个最大的项并把它放入数组中，从最后一个位置开始往前移动来实现排序的。最后一部分的复杂性在堆排序中占主导地位。循环看起来像这样：

for (i = n - 1; i > 0; i--) {
    arr[i] = deleteMax();
}

显然，循环运行 O(n) 次（准确地说是n - 1，最后一项已经到位）。堆的复杂度deleteMax是O(log n)。它通常通过删除根（堆中剩余的最大项）并将其替换为堆中的最后一项来实现，这是一个叶子，因此是最小的项之一。这个新的根几乎肯定会违反堆属性，因此您必须调用siftDown直到将其移回可接受的位置。这也具有将下一个最大项目向上移动到根的效果。请注意，与我们从树的底部buildHeap调用大多数节点的位置相比siftDown，我们现在siftDown在每次迭代时都从树的顶部调用！虽然树在收缩，但它收缩得不够快：树的高度保持不变，直到您删除了前半部分节点（当您完全清除底层时）。然后对于下一个季度，高度是h - 1。所以第二阶段的总工作量是

h*n/2 + (h-1)*n/4 + ... + 0 * 1.

注意开关：现在零工作案例对应于单个节点，而h工作案例对应于一半节点。这个总和是O(n log n)，就像buildHeap使用 siftUp 实现的低效版本一样。但是在这种情况下，我们别无选择，因为我们正在尝试排序，并且我们要求接下来删除下一个最大的项目。

综上所述，堆排序的工作是两个阶段的总和：构建 Heap的O(n)时间和O(n log n)按顺序移除每个节点的时间，因此复杂度为O(n log n)。您可以证明（使用信息论中的一些想法）对于基于比较的排序，O(n log n)是您所希望的最好的，因此没有理由对此感到失望或期望堆排序能够实现O(n) 时间限制buildHeap。

于 2013-09-11T13:22:54.310 回答
354

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

解释为什么构建堆是线性操作并不容易，您最好阅读它。

可以在这里看到对该算法的一个很好的分析。

主要思想是，在build_heap算法中，实际heapify成本并不O(log n)适用于所有元素。

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

让我们逐级计算完成的工作。

最底层有2^(h)节点，但我们不调用heapify任何一个，所以工作为0。下一层有2^(h − 1)节点，每个节点可能下移1级。在底部的第 3 级，有2^(h − 2)节点，每个节点可能会向下移动 2 级。

正如您所看到的，并非所有 heapify 操作都是O(log n)，这就是您得到的原因O(n)。

于 2012-03-18T03:39:26.430 回答
114

直观地说：

“复杂度应该是 O(nLog n)……对于我们“堆化”的每个项目，到目前为止，它有可能必须为堆的每个级别（即 log n 级别）过滤一次。”

不完全的。您的逻辑不会产生严格的限制——它过度估计了每个 heapify 的复杂性。如果从下往上构建，插入（heapify）可以比O(log(n)). 过程如下：

（步骤 1） 第一个n/2元素位于堆的底行。h=0，所以不需要 heapify。

（步骤 2） 下一个元素从底部向上排在第 1 行。, heapify 过滤 1 级。n/22h=1

（步骤i） 下一个元素从底部向上排列。, heapify 过滤器级别下降。n/2iih=ii

( Step log(n) ) 最后一个元素从底部向上排列。, heapify 过滤器级别下降。n/2log2(n) = 1log(n)h=log(n)log(n)

注意：在第一步之后，1/2元素(n/2)已经在堆中，我们甚至不需要调用 heapify 一次。另外，请注意，只有一个元素，即根，实际上会产生全部log(n)复杂性。

理论上：

N构建大小堆的总步骤n可以用数学方法写出。

在 height 处i，我们已经（上图）展示了需要调用 heapify 的元素，并且我们知道 heapify at height是. 这给出了：n/2i+1iO(i)

在此处输入图像描述

最后求和的解可以通过对众所周知的几何级数方程两边求导得到：

在此处输入图像描述

最后，x = 1/2代入上式得到2。将其代入第一个等式给出：

在此处输入图像描述

因此，总步数是大小O(n)

于 2013-08-18T03:13:59.733 回答
46

如果您通过重复插入元素来构建堆，那将是 O(n log n)。但是，您可以通过以任意顺序插入元素然后应用算法将它们“堆”成正确的顺序（当然取决于堆的类型）来更有效地创建新堆。

有关示例，请参见http://en.wikipedia.org/wiki/Binary_heap，“构建堆”。在这种情况下，您基本上从树的底层开始工作，交换父节点和子节点，直到满足堆条件。

于 2012-03-18T03:36:33.963 回答
36

已经有一些很好的答案，但我想添加一些视觉解释

在此处输入图像描述

现在，看一下图像，有高度为 0的
n/2^1 绿色节点（此处为 23/2 = 12）高度为 1的红色节点（此处为 23/4 = 6）高度为 2的蓝色节点（此处为 23/8 = 3）高度为 3的紫色节点（此处为 23/16 = 2） ，因此存在高度为h的节点 为了计算时间复杂度，让我们计算完成的工作量或每个节点执行的最大迭代次数， 现在可以注意到每个节点可以执行（最多）次迭代 == 节点的高度
n/2^2
n/2^3
n/2^4
n/2^(h+1)

Green  = n/2^1 * 0 (no iterations since no children)  
red    = n/2^2 * 1 (heapify will perform atmost one swap for each red node)  
blue   = n/2^3 * 2 (heapify will perform atmost two swaps for each blue node)  
purple = n/2^4 * 3 (heapify will perform atmost three swaps for each purple node)

所以对于任何高度为 h 的节点，完成的最大功为n/2^(h+1) * h

现在完成的总工作是 

->(n/2^1 * 0) + (n/2^2 * 1)+ (n/2^3 * 2) + (n/2^4 * 3) +...+ (n/2^(h+1) * h)  
-> n * ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) )

现在对于h的任何值，序列 

-> ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) )

永远不会超过 1因此构建堆
的时间复杂度永远不会超过O(n)

于 2019-03-03T19:29:37.210 回答
16

我们知道堆的高度是log(n)，其中 n 是元素的总数。让我们将其表示为h
当我们执行 heapify 操作时，最后一层（h）的元素甚至不会移动一个步。
倒数第二层（h-1）的元素数量为2 h-1，它们最多可以移动1层（在 heapify 期间）。
同样，对于第i层，我们有2 i个元素可以移动hi位置。

因此总移动次数：

S = 2 h * 0+2 h-1 * 1+2 h-2 * 2+...2 0 * h

S=2 h {1/2 + 2/2 2 + 3/2 3 + ... h/2 h } ------------------------ --------------------------1

这是AGP系列，解决这个问题将两边除以2
S/2 = 2 h {1/2 2 + 2/2 3 + ... h/2 h+1 } ---------- -------------------------------------------------------2

从1中减去等式2得到S/2=2 h {1/2+1/2 2 + 1/2 3 + ...+1/2 h + h/2 h+1 } S=2 h+1 { 1/2+1/2 2 + 1/2 3 + ...+1/2 h + h/2 h+1 }


现在1/2+1/2 2 + 1/2 3 + ...+1/2 h正在减少总和小于1的GP（当 h 趋于无穷大时，总和趋于 1）。在进一步分析中，让我们对总和取一个上限，即 1。

这给出：
S=2 h+1 {1+h/2 h+1 }
  =2 h+1 +h
  ~2 h +h

当h=log(n) , 2 h =n

因此S=n+log(n)
T(C)=O(n)

于 2017-02-20T20:14:46.193 回答
11

在构建堆时，假设您正在采用自下而上的方法。

  1. 您获取每个元素并将其与其子元素进行比较，以检查该对是否符合堆规则。因此，叶子被免费包含在堆中。那是因为他们没有孩子。
  2. 向上移动，叶子正上方节点的最坏情况是 1 次比较（最多只与一代子节点进行比较）
  3. 再往上走，他们的直系父母最多可以与两代孩子相提并论。
  4. 继续同一个方向，在最坏的情况下，您将对根进行 log(n) 比较。log(n)-1 为其直系子代，log(n)-2 为其直系子代，依此类推。
  5. 所以总结一下，你会得到类似 log(n) + {log(n)-1}*2 + {log(n)-2}*4 + ..... + 1*2^{( logn)-1} 这不过是 O(n)。
于 2012-07-03T10:44:33.163 回答
4

我们通过计算每个节点可以采取的最大移动来获得堆构建的运行时。所以我们需要知道每行有多少个节点，以及每个节点能走多远。

从根节点开始，下一行的节点数是前一行的两倍，因此通过回答我们多久可以将节点数加倍直到我们没有任何节点，我们得到了树的高度。或者用数学术语来说，树的高度是 log2(n)，n 是数组的长度。

为了计算一行中的节点，我们从后面开始，我们知道 n/2 个节点在底部，所以除以 2 我们得到前一行，依此类推。

基于此，我们得到了 Siftdown 方法的公式： (0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (log2(n) * 1)

最后一个括号中的项是树的高度乘以根节点处的一个节点，第一个括号中的项是底行中的所有节点乘以它们可以行进的长度，0。smart中的相同公式： 在此处输入图像描述

数学

将 n 带回我们有 2 * n，2 可以被丢弃，因为它是一个常数，并且我们有 Siftdown 方法的最坏情况运行时：n。

于 2020-06-03T16:01:40.313 回答
2

在构建堆的情况下，我们从高度 logn -1开始（其中 logn 是 n 个元素的树的高度）。对于高度为“h”的每个元素，我们将最大高度降低到（logn -h）高度。

    So total number of traversal would be:-
    T(n) = sigma((2^(logn-h))*h) where h varies from 1 to logn
    T(n) = n((1/2)+(2/4)+(3/8)+.....+(logn/(2^logn)))
    T(n) = n*(sigma(x/(2^x))) where x varies from 1 to logn
     and according to the [sources][1]
    function in the bracket approaches to 2 at infinity.
    Hence T(n) ~ O(n)
于 2015-08-20T09:26:53.170 回答
1

连续插入可以通过以下方式描述：

T = O(log(1) + log(2) + .. + log(n)) = O(log(n!))

通过八哥近似，n! =~ O(n^(n + O(1)))，因此T =~ O(nlog(n))

希望这会有所帮助，最佳方法O(n)是对给定集合使用构建堆算法（排序无关紧要）。

于 2013-09-14T10:45:28.877 回答
1

基本上，在构建堆时仅在非叶节点上完成工作......所做的工作是向下交换以满足堆条件的数量......换句话说（在最坏的情况下）数量与高度成正比节点的...总之问题的复杂性与所有非叶节点的高度之和成正比..即 (2^h+1 - 1)-h-1=nh-1=在）

于 2015-05-31T20:15:54.317 回答
1

@bcorso 已经展示了复杂性分析的证明。但是为了那些仍在学习复杂性分析的人，我要补充一点：

您最初错误的基础是对语句含义的误解，“插入堆需要 O(log n) 时间”。插入堆确实是 O(log n)，但您必须认识到 n 是插入期间堆的大小。

在将 n 个对象插入堆的上下文中，第 i 次插入的复杂度为 O(log n_i)，其中 n_i 是插入 i 时堆的大小。只有最后一次插入的复杂度为 O (log n)。

于 2017-07-09T01:28:01.450 回答
1

假设您在堆中有N个元素。那么它的高度将是Log(N)

现在您要插入另一个元素，那么复杂度将是：Log(N)，我们必须一直比较UP到根。

现在你有N+1 个元素 & height = Log(N+1)

使用归纳技术可以证明插入的复杂度为∑logi。

现在使用

日志 a + 日志 b = 日志 ab

这简化为：∑logi=log(n!)

这实际上是O(NlogN)

但

我们在这里做错了，因为在所有情况下我们都没有到达顶部。因此，在大多数情况下执行时，我们可能会发现，我们甚至不会爬到树的一半。因此，可以通过使用上面答案中给出的数学来优化此界限以具有另一个更严格的界限。

在对 Heaps 进行了详细的实验和实验之后，我才意识到这一点。

于 2018-11-20T05:36:56.307 回答
0

我真的很喜欢 Jeremy west 的解释......这里给出了另一种非常容易理解的方法 http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

因为，buildheap 依赖于使用取决于 heapify 并且使用 shiftdown 方法，这取决于所有节点的高度之和。因此，要找到由 S = summation from i = 0 to i = h of (2^i*(hi)) 给出的节点高度总和，其中 h = logn 是求解 s 的树的高度，我们得到s = 2^(h+1) - 1 - (h+1) 因为，n = 2^(h+1) - 1 s = n - h - 1 = n- logn - 1 s = O(n)，所以 buildheap 的复杂度是 O(n)。

于 2014-05-26T09:19:29.583 回答
0

“构建堆的线性时间界限，可以通过计算堆中所有节点的高度之和来显示，即虚线的最大数量。对于高度为h的完美二叉树，包含N = 2^( h+1) – 1 个节点，节点高度之和为 N – H – 1。因此它是 O(N)。

于 2015-01-15T01:17:54.563 回答
0

O(n) 的证明

证明并不花哨，而且很简单，我只证明了完全二叉树的情况，结果可以推广到完全二叉树。

于 2018-02-18T03:47:21.707 回答