为何Python heapq.heapify实现正常工作且效率优于朴素递归建堆？

首先要澄清一个很多人踩过的历史坑：heapq里的_siftup命名完全是反的，它干的就是传统算法里**子树向下调整堆（siftdown）**的活，和你写的_make_heap_invariant目标没有区别——都是让以pos为根的子树满足最小堆的不变性。

两者的渐进时间复杂度都是O(n)，没有本质的算法层级差距，所有的效率差都来自常数项开销的不同，主要在三点：

1. 赋值操作的次数差了一倍 #

你写的递归实现，每次调整父子位置用的是值交换的写法：每确认要把父和子的位置换一下，就要做两次赋值（把父的值给子，子的值给父）。
而官方的实现用了单路移位的思路：

• 一开始就把pos位置的原始值存在临时变量newitem里，全程不挪这个值
• 每一层只把当前最小的子节点向上移一层，全程只做1次赋值，沿着最小子节点的路径一直走到叶子层的空位
• 最后只做一次赋值，把newitem放到这个空位上，再用_siftdown（这部分才是真正的向上浮的逻辑）沿着从叶子到pos的路径找它的最终落点
  相当于每一层调整，你的实现要花2倍的赋值成本，堆深度越大，这个差距累积越明显。

2. 递归本身的天然开销 #

Python的函数调用是有固定成本的：每次递归都要创建栈帧、传参数、维护返回地址，这些操作的成本比纯循环的迭代高一个量级。
而且你写的递归实现本身的逻辑就有冗余：你是先和左孩子比，交换完递归处理左子树，再和右孩子比，交换完递归处理右子树，没有一次性找到父、左、右三者的最小值。举个实际的例子：

当pos位置的值是6，左孩子是4，右孩子是3时，按照正常的下沉逻辑，应该直接把最小的右孩子（值3）和6交换，然后递归处理右位置的6就够了。但你的实现会先把6和左孩子的4交换（把6挪到左位置），递归处理完左子树后，再把现在pos位置的4和右孩子的3交换，把4挪到右位置，最后递归处理右位置的4。整个过程多了一次交换、多了一次递归调用，都是完全没必要的开销。
官方实现的循环里，每一层都会先找到左右孩子里更小的那个，直接做移位，不会出现这种重复移动的情况。

3. 大量细粒度的常量优化 #

官方实现里所有的位置计算都用位运算完成（比如算父节点位置用(pos - 1) >> 1），比普通的整数除法执行快；循环的边界判断都是提前固化的，没有冗余的越界检查。这些小优化单看一次可能没感觉，但在大列表上累积起来，速度差会非常明显。

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