algorithm - 如何建立堆的时间复杂度为O(n)？

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

将项目插入到堆中是O(log n)，并且插入重复n/2次(其余为叶子，并且不能违反heap属性)。因此，我认为这意味着复杂度应为O(n log n)。

换句话说，对于我们“堆砌”的每个项目，它有可能不得不针对到目前为止的堆的每个级别(即log n个级别)过滤一次。

我想念什么？

最佳答案

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

如何实现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属性为止:

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)的Taylor级数的导数。

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)。但是在这种情况下，我们别无选择，因为我们正在尝试排序，因此我们要求下一个最大的项目被删除。
总而言之，堆排序的工作是两个阶段的总和:buildHeap的O(n)时间和 O(n log n)以顺序删除每个节点的时间，因此复杂度为O(n log n)。您可以证明(使用信息论中的一些想法)，对于基于比较的排序，无论如何，O(n log n)是您所希望的最好的选择，因此没有理由对此感到失望或期望堆排序可以实现buildHeap的时间限制为O(n)。