Heapify、Heap-Sort与Construct Heap区别及底层实现疑问

1. 三类操作的核心定义与差异 #

• Max Heapify：堆操作的最小原子单元，前置条件是当前节点的左右子树都已经满足最大堆性质，作用是把当前节点和它的子节点比较，若当前节点小于子节点，就把它和最大的子节点交换，再递归/迭代调整被交换的子节点，直到以当前节点为根的子树完全符合最大堆性质，单次调用时间复杂度为O(h)，h为当前节点对应的子树高度。
• Construct Heap（建堆）：目标是把完全无序的数组转换为合法的最大堆。工业界标准实现是自下而上遍历所有非叶子节点（从索引为n//2 -1的节点开始倒序遍历到0），对每个节点调用Max Heapify，时间复杂度为O(n)。你提到的自上而下建堆是另一种实现，也就是逐个把元素插入堆尾再上浮调整，时间复杂度为O(nlogn)，性能不如标准实现，所以很少用。
• Heap Sort（堆排序）：基于堆的排序算法，完整流程分两步：1. 调用建堆逻辑把输入数组转换为最大堆；2. 循环执行以下操作直到堆大小为1：交换堆顶（数组索引0，当前堆的最大值）和当前堆的最后一个元素，把堆大小减1（相当于把最大值固定到数组末尾的有序区），对新的堆顶调用Max Heapify调整堆性质。整体时间复杂度为O(nlogn)。

2. 原有认知正误验证 #

你的认知部分成立，具体说明如下：

• 关于Max Heapify和自上而下建堆相似：该认知成立，自上而下建堆的调整逻辑确实和Max Heapify的下沉/上浮逻辑高度相似，但要注意标准建堆用的是自下而上的实现，和Max Heapify是调用与被调用的关系，不是相似关系。
• 关于堆排序和建堆逻辑接近，仅多了堆首移到末尾的步骤：该认知部分成立，堆排序的调整阶段确实是基于Max Heapify的反复调用，仅多了堆顶交换和堆收缩的步骤，但堆排序整体包含前置的建堆步骤，逻辑上比建堆更复杂。

3. 处理对象说明 #

三类操作的处理对象都是普通数组，不存在实际的二叉树数据结构实体。我们只是通过固定的索引映射规则，用数组模拟完全二叉树的逻辑结构：

• 索引为i的节点，左子节点索引为2*i + 1
• 索引为i的节点，右子节点索引为2*i + 2
• 索引为i的节点，父节点索引为(i - 1) // 2
  所有操作本质都是对数组元素进行重排，没有任何二叉树节点的创建、指针修改等操作。

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