堆排序构建堆为何用sink而非swim？《算法4》相关疑问

先明确堆的本质是完全二叉树，叶子节点本身就符合堆的规则（没有子节点可比较），所以构建堆根本不用处理叶子层。

核心区别在操作次数的复杂度 #

• 用sink()从右到左构建：
  我们从倒数第二层的第一个节点（也就是索引N/2的位置，N为总节点数）开始，向左逐个处理每个节点，调用sink()让节点下沉到合适位置。每个节点需要下沉的次数等于它的高度（从叶子层往上数，叶子层高度算1）。
  对于完全二叉树，高度为h的节点数量是2^(h-1)，把所有节点的下沉次数累加后，总复杂度是O(N)——线性级，实际总次数约等于N减去树的叶子节点数，远低于NlogN量级。

• 用swim()从左到右构建：
  从第二个节点开始，向右逐个处理每个节点，调用swim()让节点上浮到合适位置。每个节点需要上浮的次数等于它的深度（从根节点往下数，根节点深度算1）。
  深度为d的节点数量是2^(d-1)，把所有节点的上浮次数累加后，总复杂度是O(NlogN)——线性对数级，节点数越多，这个次数比sink方式多出的比例越大。

直观例子对比 #

比如N=16的堆：

• sink方式：处理索引8到1的节点，总操作次数约16次；
• swim方式：处理索引2到16的节点，总操作次数要50多次，差距非常明显。

为什么你会觉得效果相近？ #

在节点数极少的小堆里，两种方式的操作次数差异不突出，比如N=4时，sink总次数3次，swim总次数4次，差不了多少。但当节点数达到十万、百万级时，O(N)和O(NlogN)的性能差距会被放大——sink方式的效率能高出好几倍。

内容的提问来源于stack exchange，提问作者Lucio Sun