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

Question

有人可以帮助解释如何构建堆是O(n)复杂性？

将项插入堆中O(log n),并且插入重复n/2次(其余为叶,并且不能违反堆属性).所以,这意味着复杂性应该是O(n log n),我想.

换句话说,对于我们"堆积"的每个项目,它有可能必须针对堆的每个级别过滤一次(这是log n级别).

我错过了什么？

Answer 1

我认为这个主题有几个问题:

• 你如何实现buildHeap所以它在O(n)时间运行？
• 如何正确实现buildHeap在O(n)时间运行？
• 为什么同样的逻辑不能使堆排序在O(n)时间而不是O(n log n)中运行？

通常情况下,这些问题的答案集中在之间的区别buildHeap和buildHeap.作出正确的选择之间buildHeap以及siftUp重要的是获得O(n)的性能siftDown,但没有帮助一个明白之间的差别siftUp和siftDown一般.事实上,两者的正确实施buildHeap和buildHeap将仅使用heapSort.在buildHeap只需要操作来执行插入到现有的堆,所以它会被用于实现使用二进制堆,例如优先级队列.

我写这篇文章来描述最大堆如何工作.这是通常用于堆排序或优先级队列的堆类型,其中较高的值表示较高的优先级.最小堆也很有用; 例如,当按升序检索具有整数键的项目或按字母顺序检索字符串时.原则完全一样; 只需切换排序顺序即可.

所述堆属性指定在二元堆的每个节点必须至少为它的两个孩子的一样大.特别是,这意味着堆中的最大项目位于根.向下筛选和筛选在相反方向上基本上是相同的操作:移动违规节点直到它满足堆属性:

• heapSort 交换一个太小的节点与其最大的子节点(从而将其向下移动),直到它至少与它下面的两个节点一样大.
• siftDown 交换一个与其父节点过大的节点(从而将其向上移动),直到它不大于其上方的节点.

所需的操作的数量siftUp和siftDown正比于节点可能必须移动的距离.因为siftUp,它是到树底部的距离,因此siftDown对于树顶部的节点来说是昂贵的.因此siftUp,工作与到树顶的距离成比例,因此siftDown对于树底部的节点来说是昂贵的.虽然在最坏的情况下两个操作都是O(log n),但在堆中,只有一个节点位于顶部,而一半节点位于底层.所以,如果我们必须对每个节点应用一个操作,我们宁愿siftDown过度也不应该太令人惊讶siftUp.

该siftUp函数接受一组未排序的项并移动它们,直到它们都满足heap属性,从而生成一个有效的堆.siftDown使用我们描述的操作siftUp和buildHeap操作可能有两种方法.

1. 从堆的顶部开始(数组的开头)并调用buildHeap每个项目.在每一步中,先前筛选的项(数组中当前项之前的项)形成有效堆,并筛选下一项将其置于堆中的有效位置.筛选每个节点后,所有项都满足堆属性.

2. 或者,向相反方向前进:从阵列末端开始向前移动.在每次迭代中,您将一个项目向下筛选,直到它位于正确的位置.

这两种解决方案都将产生有效的堆.问题是:哪种实施siftUp更有效？不出所料,这是第二次使用的操作siftDown.

设h = log n表示堆的高度.该siftUp方法所需的工作由总和给出

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

总和中的每个项具有给定高度处的节点必须移动的最大距离(底层为零,根为h)乘以该高度处的节点数.相反,调用buildHeap每个节点的总和是

(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).

接下来的问题是:如果可以siftDown在线性时间运行,为什么堆排序需要O(n log n)时间？堆排序包括两个阶段.首先,我们调用siftUp数组,如果实现最佳,则需要O(n)时间.下一步是重复删除堆中最大的项并将其放在数组的末尾.因为我们从堆中删除了一个项目,所以在堆的末尾之后总是存在一个开放点,我们可以存储该项目.因此,堆排序通过连续删除下一个最大项并将其放入从最后位置开始并向前移动的数组来实现排序顺序.最后一部分的复杂性在堆排序中占主导地位.循环看起来像这样:

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

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

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

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

总之,堆排序的工作是两个阶段的总和: buildHeap的O(n)时间和O(n log n)按顺序删除每个节点,因此复杂度为O(n log n).您可以证明(使用信息理论中的一些想法),对于基于比较的排序,O(n log n)是您可能希望的最佳方式,因此没有理由对此感到失望或期望堆排序实现O(n)时间限制siftDown.

Answer 2

你的分析是正确的.但是,它并不紧张.

解释为什么构建堆是一个线性操作并不是很容易,你应该更好地阅读它.

一个伟大的分析算法可以看出这里.

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

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

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

在最底层,有2^(h)节点,但我们不会调用其中heapify任何一个,因此工作为0.在下一级别有2^(h ? 1)节点,每个节点可能向下移动1级.在底部的第3层,有2^(h ? 2)节点,每个节点可能向下移动2个级别.

正如您所看到的,并非所有的堆化操作都是如此O(log n),这就是您获得的原因O(n).

Answer 3

直观:

"复杂性应该是O(nLog n)...对于我们"堆积"的每个项目,它有可能必须为目前为止的堆的每个级别过滤掉一次(这是log n级别)."

不完全的.你的逻辑不会产生严格的限制 - 它估计每个堆的复杂性.如果从下到上构建,插入(heapify)可能远远小于O(log(n)).过程如下:

(步骤1) 第一个n/2元素位于堆的底行.h=0,所以不需要heapify.

(步骤2) 下一个元素从底部向上行1.,堆积过滤器1级下来.n/22h=1

(步骤i) 下一个元素从底部向上排.,堆积过滤器级别.n/2iih=ii

(步骤log(n)) 最后一个元素从底部向上排.,堆积过滤器级别.n/2log2(n) = 1log(n)h=log(n)log(n)

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

从理论上讲:

N构建大小堆的Total步骤n可以用数学方法写出来.

在高处i,我们已经显示(上图)将有需要调用heapify的元素,并且我们知道在高度处的堆积是.这给出了:n/2i+1iO(i)

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

最后,插入x = 1/2上面的等式得出2.将其插入第一个等式给出:

因此,步骤的总数是大小的 O(n)

Answer 4

如果通过重复插入元素来构建堆,那么它将是O(n log n).但是,您可以通过以任意顺序插入元素然后应用算法将它们"堆积"到正确的顺序(当然,取决于堆的类型),从而更有效地创建新堆.

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

Answer 5

我们通过计算每个节点可以进行的最大移动来获得堆构建的运行时间。所以我们需要知道每行中有多少个节点以及每个节点距离它们有多远。

从根节点开始，下一行的节点数是前一行的两倍，因此通过回答我们多久可以将节点数加倍，直到没有任何节点为止，我们就得到了树的高度。或者用数学术语来说，树的高度是 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。

Answer 6

简答

构建二进制堆需要O(n)时间Heapify()。

当我们将堆中的元素逐一添加并在每一步都满足堆属性（最大堆或最小堆）时，总时间复杂度将为O(nlogn)。因为二叉堆的一般结构是完全二叉树。因此堆的高度是h = O(logn)。所以堆中一个元素的插入时间相当于树的高度即。O(h) = O(logn)。对于n元素来说，这需要O(nlogn)时间。

现在考虑另一种方法。为了简单起见，我假设我们有一个最小堆。所以每个节点都应该小于它的子节点。

1. 将完全二叉树的骨架中的所有元素相加。这需要O(n)时间。
2. 现在我们只需要以某种方式满足最小堆属性。
3. 由于所有叶元素都没有子元素，因此它们已经满足堆属性。叶子元素的总数是ceil(n/2)其中 n 是树中存在的元素总数。
4. 现在，对于每个内部节点，如果它大于其子节点，则以自下而上的方式将其与最小子节点交换。O(1)每个内部节点都需要时间。Note:我们不会像插入那样将值交换到根。我们只需交换一次，以便以该节点为根的子树是一个适当的最小堆。
5. 在二叉堆的基于数组的实现中，我们有parent(i) = ceil((i-1)/2)和 的子级由和i给出。因此通过观察我们可以说数组中的最后一个元素将是叶节点。深度越深，节点的索引就越多。我们将重复. 通过这种方式，我们确保以自下而上的方式进行此操作。总的来说，我们最终将维持最小堆属性。2*i + 12*i + 2ceil(n/2)Step 4array[n/2], array[n/2 - 1].....array[0]
6. 所有n/2元素的第 4 步都需要O(n)时间。

因此，使用这种方法的 heapify 的总时间复杂度将为 O(n) + O(n) ~ O(n)。

Answer 7

我们知道堆的高度是log(n),其中n是元素的总数.    让我们将其表示为h
当我们执行heapify操作时,最后一级(h)的元素即使只有一个也不会移动步.
   倒数第二级(h-1)的元素数量为2 ^h-1,它们可以在最大1级移动(在堆化期间).
   类似地,对于我^个,水平我们有2个^我元件,其可以移动喜位置.

因此总移动次数= S = 2 ^h*0 + 2 ^h-1*1 + 2 ^h-2*2 + ... 2 ⁰*h

                                               S = 2 ^小时 {1/2 + 2/2 ² + 3/2 ³ + ... h/2 ^小时 } ----------------------- -------------------------- 1
这是AGP系列,为了解决这个问题,将双方分成2
                                               S/2 = 2 ^h {1/2 ² + 2/2 ³ + ... h/2 ^{h + 1} } --------------------------------- ---------------- 2 从1中
减去等式2给出S/2 = 2 ^h { 1/2 + 1/2 ² + 1/2 ³ + ... + 1/2 ^h + h/2 ^{h + 1} } S = 2 ^{h + 1} { 1/2 + 1/2 ² + 1/2 ³ + ... + 1/2 ^h + h/2 ^{h + 1} } 现在1/2 + 1/2 ² + 1/2 ³ + ... + 1/2 ^h正在减小GP,其总和小于1(当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)
                                               
                                               



                    

Answer 8

在构建堆时,假设您采用自下而上的方法.

1. 您将每个元素与其子元素进行比较,以检查该元素是否符合堆规则.因此,叶子可以免费包含在堆中.那是因为他们没有孩子.
2. 向上移动,叶子正上方的节点的最坏情况将是1比较(在最大值它们将与仅仅一代的孩子进行比较)
3. 进一步向上,他们的直系父母最多可以与两代孩子进行比较.
4. 继续朝着相同的方向,在最坏的情况下,您将对根进行log(n)比较.并为其直接子节点记录(n)-1,为其直接子节点记录log(n)-2,依此类推.
5. 总而言之,你得到的东西就像log(n)+ {log(n)-1}*2 + {log(n)-2}*4 + ..... + 1*2 ^ {( logn)-1}这只是O(n).

Answer 9

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

现在，看看在图像中，有
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/4^3 * 3  

因此，对于任何高度为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）