向堆中添加元素时为何不从根节点执行Heapify？

核心结论 #

直接在添加元素后对整个堆执行Heapify确实实现起来更简单，但这是一种性能极差的做法，完全没必要——你的顾虑其实是对bubble up操作的误解。

具体解释 #

• Bubble Up的实际逻辑没有你想的复杂
  向堆中添加元素时，我们会把新元素放在堆的最末尾（对应数组的最后一位）。此时原堆的所有节点都满足堆属性，只有新元素和它的父节点这条路径可能违反规则。bubble up只需要逐层向上比较交换，直到新元素找到合适的位置即可——根本不需要检查左右子节点，更不需要对左右子树执行Heapify。整个过程只会影响新元素到根节点的这条路径，不会引发大量堆属性冲突。

• 时间复杂度的差距天差地别

  • Bubble up的时间复杂度是O(log n)：堆的高度是log₂(n)，最多只需要上浮这么多层。
  • 全堆Heapify的时间复杂度是O(n)：虽然单次O(n)看起来不算大，但如果是高频添加元素的场景（比如多次插入），累计性能差距会非常夸张。比如插入k个元素，bubble up的总时间是O(k log n)，而全堆Heapify是O(k n)，当n较大时后者的开销会直接拖垮程序。

• Heapify的适用场景不对
  Heapify设计出来是用来把完全无序的数组转换成堆结构的，而添加元素后的堆只是多了一个末尾元素，整体几乎是合法的堆。用全堆Heapify处理这种几乎有序的结构，属于用重型工具干轻活，完全是性能浪费。

总结 #

bubble up操作的复杂度远低于你的想象，它只会处理一条路径，不会引发大量冲突；而全堆Heapify虽然实现简单，但性能代价太高，实际工程中绝不会用这种方式处理堆的插入操作。

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