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

• 你如何实现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。