如何建立堆的时间复杂度为O（n）？

#1 楼

我认为此主题中存在几个问题：

如何实现buildHeap使其在O（n）时间运行？
如何显示buildHeap在O（n）时间内运行
为什么相同的逻辑不能使堆排序在O（n）时间而不是O（n log n）中运行？

如何实现buildHeap所以它运行时间为O（n）？
通常，对这些问题的答案集中在siftUp和siftDown之间。在siftUp和siftDown之间做出正确的选择对于获得buildHeap的O（n）性能至关重要，但通常无助于帮助您了解buildHeap和heapSort之间的区别。实际上，buildHeap和heapSort的正确实现都只会使用siftDown。 siftUp操作仅需要在现有堆中执行插入操作，因此将用于例如使用二进制堆来实现优先级队列。
我已经写了这本书来描述最大堆的工作方式。这是堆的类型，通常用于堆排序或优先级队列，其中较高的值表示较高的优先级。最小堆也很有用；例如，当使用整数键以升序或字符串以字母顺序检索项目时。原理完全相同；只需切换排序顺序即可。
heap属性指定二进制堆中的每个节点必须至少与其两个子节点一样大。特别是，这意味着堆中最大的项位于根。向下筛选和向上筛选本质上是在相反方向上的相同操作：移动一个有问题的节点，直到它满足heap属性：


siftDown交换一个太大的子节点和最大的子节点（

siftUp与其父节点交换一个太大的节点（从而将其向上移动），直到不大于该节点的大小为止。节点上方。

siftDown和siftUp所需的操作次数与节点可能必须移动的距离成比例。对于siftDown，它是到树底部的距离，因此siftDown对于树顶部的节点而言代价昂贵。使用siftUp时，功与到树顶部的距离成比例，因此siftUp对于树底部的节点来说是昂贵的。尽管在最坏的情况下两个操作都为O（log n），但在堆中，只有一个节点位于顶部，而一半的节点位于底层。因此，如果我们必须对每个节点都执行一个操作，那么我们宁愿使用siftDown而不是siftUp，也就不足为奇了。
buildHeap函数接受未排序项的数组并将其移动，直到它们全部满足heap属性为止，从而产生有效的堆。使用我们已经介绍过的buildHeap和siftUp操作，可以对siftDown采取两种方法。


从堆的顶部（数组的开头）开始，然后调用siftUp每个物品。在每个步骤中，先前筛选的项目（数组中当前项目之前的项目）形成有效堆，然后向上筛选下一个项目将其放入堆中的有效位置。筛选完每个节点后，所有项都满足heap属性。或者，朝相反的方向前进：从数组的末尾开始，向后移到最前面。在每次迭代时，您都会向下筛选项目，直到将其放置在正确的位置。


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）。通常通过删除根（堆中剩余的最大项）并将其替换为堆中的最后一项（叶），因此是最小项之一来实现。这个新的根几乎肯定会违反heap属性，因此必须调用siftDown，直到将其移回可接受的位置为止。这还具有将下一个最大的项目移到根目录的作用。请注意，与buildHeap相反，对于大多数节点，我们从树的底部调用siftDown，而现在每次迭代从树的顶部调用siftDown！尽管树正在收缩，但收缩得不够快：树的高度保持恒定，直到您删除了节点的前半部分（完全清除了底层）。那么对于下一季度，高度为h-1。因此，第二阶段的总功为

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

注意开关：现在零工作例对应一个节点，h工作例对应一半节点。就像使用siftUp实现的低效率版本buildHeap一样，该总和为O（n log n）。但是在这种情况下，我们别无选择，因为我们试图进行排序，并且我们需要接下来移除下一个最大的项目。
总而言之，堆排序的工作是两个阶段的总和：O（n）时间为buildHeap和O（n log n）依次删除每个节点，因此复杂度为O（n log n）。您可以证明（使用信息论的一些思想），对于基于比较的排序，无论如何，O（n log n）是您所希望的最好的选择，因此没有理由对此感到失望或期望堆排序可以实现buildHeap的O（n）时限。

#2 楼

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

解释为什么构建堆是线性操作不是一件容易的事，您应该更好地阅读它。

可以在此处对算法进行很好的分析。


主要思想是，在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)的原因。 br />

#3 楼

直观地：


“对于我们“堆砌”的每个项目，复杂度应为O（nLog n）...，对于每个级别，它都有可能必须过滤一次堆到目前为止（这是对数n个级别）。“


不太正确。您的逻辑不会产生严格的界限，而是会高估每个堆的复杂性。如果从下至上构建，则插入（堆集）可能比O(log(n))小得多。过程如下：

（步骤1）第一个n/2元素位于堆的底部行。 h=0，因此不需要heapify。（步骤2）接下来的n/22元素从底部开始在第1行。 h=1，heapify过滤器向下1级。

（步骤i）
下一个n/2i元素从底部开始进入i行。 h=i，heapify过滤器将i级别降低。

（步骤log（n））最后一个n/2log2(n) = 1元素从底部开始排入log(n)行。 h=log(n)，heapify过滤器log(n)降低了级别。

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


理论上：

构建一个堆的总步骤N大小为n，可以用数学方式写出。

在高度i处，我们（上面）显示将有n/2i+1个元素需要调用heapify，我们知道在高度i处的heapify是O(i)。这给出了：





对最后一个求和的解可以通过采用众所周知的几何级数的两侧的导数来找到。等式：





最后，将x = 1/2插入上述等式中，得出2。将其代入第一个方程式可得到：





因此，步骤的总数为O(n)

#4 楼

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

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

#5 楼

已经有了一些不错的答案，但我想添加一些视觉上的解释



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

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）

#6 楼

在构建堆时，可以说您正在采用自下而上的方法。


您将每个元素与它的子元素进行比较，以检查该对是否符合堆规则。因此，叶子是免费包含在堆中的。那是因为他们没有孩子。
向上移动，叶子上方节点的最坏情况是1个比较（最多可以将它们与一代孩子进行比较）
进一步向上移动，其直系父母最多可以与两代孩子相比。
朝着同一方向发展，在最坏的情况下，您将获得根的log（n）比较。而log（n）-1为其直系子代，log（n）-2为其直系子代，等等。 ）-1} * 2 + {log（n）-2} * 4 + ..... + 1 * 2 ^ {（logn）-1}，不过是O（n）。

#7 楼

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

因此，移动总数= S = 2h * 0 + 2h-1 * 1 + 2h-2 * 2 +。 ..20 * h

s = 2h {1 / 2h {1/2 + 2/22 + 3/23 + ... h / 2h} -------------- ----------------------------------- 1
这是AGP系列，解决了两者的分歧边2
边S / 2 = 2h {1/22 + 2/23 + ... h / 2h + 1} -------------------- ----------------------------- 2
从1中减去方程2得到
S / 2 = 2h { 1/2 + 1/22 + 1/23 + ... + 1 / 2h + h / 2h + 1}
S = 2h + 1 {1/2 + 1/22 + 1/23 + ... + 1 / 2h + h / 2h + 1}
现在1/2 + 1/22 + 1/23 + ... + 1 / 2h正在减小总和小于1的GP（当h趋于无穷大时，总和趋于1）。在进一步分析中，让我们对1的总和进行上限。
这样得出S = 2h + 1 {1 + h / 2h + 1}等于2h + 1 + h = 2h + 1 + h〜2h +具有h = log（ n），2h = n因此S = n + log（n）T（C）= O（n）

#8 楼

在构建堆的情况下，我们从高度开始，
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)

#9 楼

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

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

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

希望有帮助，O(n)的最佳使用方式给定集合的构建堆算法（顺序无关紧要）。

#10 楼

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

#11 楼

@bcorso已经展示了复杂性分析的证据。但是，为了那些仍在学习的复杂性分析，我要添加以下内容：

您原始错误的基础是由于对语句含义的错误解释，“插入到堆中需要O （log n）时间”。插入到堆中确实是O（log n），但是您必须认识到n是插入期间堆的大小。

将n个对象插入到堆中的复杂性第i次插入的值为O（log n_i），其中n_i是在插入i时堆的大小。只有最后一个插入的复杂度为O（log n）。

#12 楼

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

现在您要插入另一个元素，那么复杂度将是：Log（N），我们必须一直向上比较根。

现在您拥有N + 1个元素，并且高度= Log（N + 1）

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

现在使用


log a + log b =日志ab


这可以简化为：∑logi = log （n！）

实际上是O（NlogN）

但是

我们在这里做错了，就像在所有情况下一样
因此，在执行大多数时间时，我们可能会发现，我们甚至没有走到树的一半。因此，可以使用上面答案中给出的数学方法将此边界优化为更严格的边界。

经过对Heaps进行了详细的实验之后，我才意识到了这一认识。

#13 楼

我真的很喜欢杰里米·韦斯特（Jeremy West）的解释。...此处提供了另一种非常容易理解的方法http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

因为，buildheap取决于使用取决于heapify，并使用shiftdown方法，该方法取决于所有节点的高度之和。因此，要找到由
S =从i = 0到（2 ^ i *（hi））的i = h的总和给出的节点的高度之和，其中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）。

#14 楼

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

#15 楼

O（n）的证明

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

#16 楼

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

从根节点开始，下一行的节点数是前一行的两倍，因此，通过回答我们可以将节点数增加一倍，直到没有剩余的节点数，我们才能得到树的高度。
或者用数学术语来说，树的高度是log2（n），n是数组的长度。

要计算一行中的节点，我们从背面开始，我们知道n / 2个节点位于底部，因此将其除以2得到上一行，依此类推。

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

最后一个括号中的项是高度乘以树的根上的一个节点，则第一个括号中的项是底行乘积中的所有节点取决于行进的长度，0。
智能中的公式相同：




将n带回2 n，2可以被丢弃，因为它的常量和tada是Siftdown方法的最坏情况运行时：n。

#17 楼

认为你在犯错。看一下这个：http://golang.org/pkg/container/heap/建立堆不是O（n）。但是，插入是O（lg（n）。如果您设置了b / c的堆大小，我假设初始化是O（n），则堆需要分配空间并设置数据结构。
要放入堆中的n个项目，然后是的，每个插入项都是lg（n），并且有n个项目，因此您得到n * lg（n），如u所述