有人能解释一下构建堆的复杂性吗？
将项插入到堆中是O（logn），并且插入被重复n/2次（剩余的是叶子，不能违反堆属性）。所以，我认为这意味着复杂性应该是O（n log n）。
换言之，对于我们“heapify”的每个项目，它有可能必须为堆的每个级别（即logn级别）过滤（即筛选）一次。
我错过了什么？
当前回答
@bcorso已经证明了复杂性分析的证据。但为了那些还在学习复杂性分析的人，我想补充一下：
您最初错误的基础是对语句含义的误解，“插入堆需要O（logn）时间”。插入到堆中确实是O（logn），但您必须认识到n是插入过程中堆的大小。
在向堆中插入n个对象的情况下，第i次插入的复杂性为O（logn_i），其中n_i是插入i时堆的大小。只有最后一次插入的复杂度为O（log n）。
其他回答
在构建堆时，假设您采用的是自下而上的方法。
您获取每个元素并将其与子元素进行比较，以检查该元素对是否符合堆规则。因此，叶被免费包含在堆中。那是因为他们没有孩子。向上移动，叶子正上方节点的最坏情况是1次比较（最多只能与一代孩子进行比较）再往上看，他们的直系父母最多可以与两代子女相比。继续朝着相同的方向，在最坏的情况下，您将对根进行log（n）比较。并且log（n）-1用于其直系子代，log（n）-2用于其直系子女，依此类推。所以总结起来，你会得到类似log（n）+{log（n（n）-1}*2+{log（n）-2}*4+…..+1*2^{（logn）-1}，它只是O（n）。
你的分析是正确的。然而，它并不紧密。
要解释为什么构建堆是一个线性操作并不容易，您应该更好地阅读它。
这里可以看到对算法的详细分析。
主要思想是，在build_heap算法中，所有元素的实际堆化成本不是O（logn）。
当调用heapify时，运行时间取决于进程终止之前元素在树中向下移动的距离。换句话说，它取决于堆中元素的高度。在最坏的情况下，元素可能会一直下降到叶级别。
让我们一级一级地计算完成的工作。
在最底层，有2^（h）个节点，但我们没有对这些节点调用heapify，因此功为0。在下一级有2^（h−1）个节点，每个节点可能向下移动一级。在从底部开始的第3层，有2^（h−2）个节点，每个节点可能向下移动2层。
正如您所看到的，并不是所有的heapify操作都是O（logn），这就是为什么您会得到O（n）。
@bcorso已经证明了复杂性分析的证据。但为了那些还在学习复杂性分析的人，我想补充一下：
您最初错误的基础是对语句含义的误解，“插入堆需要O（logn）时间”。插入到堆中确实是O（logn），但您必须认识到n是插入过程中堆的大小。
在向堆中插入n个对象的情况下，第i次插入的复杂性为O（logn_i），其中n_i是插入i时堆的大小。只有最后一次插入的复杂度为O（log n）。
连续插入可通过以下方式描述：
T = O(log(1) + log(2) + .. + log(n)) = O(log(n!))
通过starling近似，n！=~O（n^（n+O（1））），因此T=~O（nlog（n））
希望这有帮助，O（n）的最佳方式是对给定集合使用构建堆算法（排序无关紧要）。
我认为这个话题中隐藏着几个问题：
如何实现buildHeap，使其在O（n）时间内运行？当正确实现时，如何显示buildHeap在O（n）时间内运行？为什么同样的逻辑不能使堆排序在O（n）时间而不是O（n log n）时间内运行？
如何实现buildHeap，使其在O（n）时间内运行？
通常，这些问题的答案集中于向上筛选和向下筛选之间的区别。在siftUp和siftDown之间做出正确的选择对于获得buildHeap的O（n）性能至关重要，但这无助于理解buildHeap和heapSort之间的区别。实际上，buildHeap和heapSort的正确实现只会使用siftDown。siftUp操作只需要在现有堆中执行插入操作，因此它将用于使用二进制堆实现优先级队列。
我写这篇文章是为了描述最大堆是如何工作的。这是通常用于堆排序或优先级队列的堆类型，其中较高的值表示较高的优先级。最小堆也是有用的；例如，当检索具有按升序排列的整数键或按字母顺序排列的字符串的项目时。原则完全相同；只需切换排序顺序。
heap属性指定二进制堆中的每个节点必须至少与其两个子节点一样大。特别是，这意味着堆中最大的项位于根。向下筛选和向上筛选基本上是相反方向的相同操作：移动有问题的节点，直到它满足堆属性：
向下筛选将太小的节点与其最大的子节点进行交换（从而将其向下移动），直到它至少与其下的两个节点一样大。siftUp将过大的节点与其父节点交换（从而将其上移），直到其不大于其上方的节点。
向下筛选和向上筛选所需的操作数与节点可能移动的距离成比例。对于向下筛选，它是到树底部的距离，因此向下筛选对于树顶部的节点来说是昂贵的。使用siftUp，工作与到树顶部的距离成正比，因此对于树底部的节点来说，siftUp是昂贵的。尽管在最坏的情况下，两个操作都是O（log n），但在堆中，只有一个节点位于顶层，而一半的节点位于底层。因此，如果我们必须对每个节点应用一个操作，那么我们更倾向于向下筛选而不是向上筛选，这并不奇怪。
buildHeap函数获取未排序项的数组，并移动它们，直到它们都满足堆属性，从而生成有效的堆。有两种方法可以用于buildHeap，使用我们已经描述的siftUp和siftDown操作。
从堆的顶部（数组的开头）开始，并对每个项目调用siftUp。在每一步中，先前筛选的项目（数组中当前项目之前的项目）形成一个有效的堆，并且向上筛选下一个项目将其置于堆中的有效位置。筛选每个节点后，所有项都满足堆属性。或者，朝相反的方向走：从阵列的末端开始，向后移动到前面。在每次迭代中，您都要筛选一个项目，直到它位于正确的位置。
buildHeap的哪个实现更有效？
这两种解决方案都将生成有效的堆。毫不奇怪，更有效的是使用向下筛选的第二个操作。
设h=logn表示堆的高度。向下筛选方法所需的工作由总和给出
(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）。
我们如何证明向下筛选方法的和确实是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（logn）。它通常是通过删除根（堆中剩余的最大项）并用堆中的最后一个项（即叶，因此也是最小项之一）来实现的。这个新的根几乎肯定会违反堆属性，因此必须调用siftDown，直到将其移回可接受的位置。这还具有将下一个最大项目向上移动到根的效果。注意，与buildHeap不同，对于大多数节点，我们从树的底部调用siftDown，现在我们在每次迭代时都从树的顶部调用siftDown！虽然树正在收缩，但收缩速度不够快：树的高度保持不变，直到移除前一半节点（当完全清除底层时）。接下来的四分之一，高度是h-1。所以第二阶段的总工作量是
h*n/2 + (h-1)*n/4 + ... + 0 * 1.
注意切换：现在零工作情况对应于单个节点，而h工作情况对应一半节点。这个和是O（n log n），就像使用siftUp实现的buildHeap的低效版本一样。但在这种情况下，我们别无选择，因为我们正在尝试排序，我们要求接下来删除下一个最大的项目。
总之，堆排序的工作是两个阶段的总和：buildHeap的O（n）时间和按顺序删除每个节点的O（nlogn），因此复杂性为O（nlog n）。您可以证明（使用信息理论中的一些想法），对于基于比较的排序，O（n log n）是您所希望的最佳排序，因此没有理由对此感到失望，也没有理由期望堆排序达到buildHeap所能达到的O（n）时间限制。
