C++实现堆排序算法 _ heapify过程与数组调整逻辑【详解】

堆排序里的那个 heapify 操作，启动位置必须是最后一个非叶子节点，也就是下标 n/2 - 1，然后自底向上逐个下沉——这个顺序错不得。叶子节点压根没有子节点，不需要调整；要是从根节点开始正向往下堆化，刚调整好的子树结构，一上来就被父节点给破坏了。

堆排序的 heapify 不是“从上往下堆化”，而是从最后一个非叶子节点开始、自底向上逐个下沉——这点错，整个数组就建不出最大堆。

为什么必须从 last_non_leaf 开始倒着调用 heapify

数组表示完全二叉树时，下标从 0 开始，最后一个非叶子节点位置是 (n / 2) - 1（n 为数组长度）。叶子节点无需调整，因为它们没有子节点可比较；若从根（下标 0）开始正向 heapify，会导致子树已调整好的结构被父节点下沉破坏。

常见错误现象：heapify(arr, 0, n) 单独调用一次，结果数组不是最大堆——它只保证根满足堆性质，不保证左右子树已是堆。

正确做法：

• 循环变量 i 从 n/2 - 1 递减到 0
• 对每个 i 调用 heapify(arr, i, n)
• 确保每次调用时，以 i 为根的子树的左右子树都已是堆（由后续迭代保障）

heapify 函数里怎么选最大值并交换

heapify 的核心是“找当前节点与其左右孩子的最大值，若最大值不是自己，就交换，然后递归下沉”。注意三个关键点：

• 左孩子下标固定为 2 * i + 1，右孩子为 2 * i + 2（0-indexed）
• 必须先检查左孩子是否存在（left < heap_size），再比右孩子；否则越界访问
• 找到最大值下标后，仅当它 ≠ 当前 i 时才交换，并继续对那个孩子位置调用 heapify

示例片段（关键逻辑）：

void heapify(vector& arr, int i, int heap_size) {    int largest = i;    int left = 2 * i + 1;    int right = 2 * i + 2;
if (left < heap_size && arr[left] > arr[largest])    largest = left;if (right < heap_size && arr[right] > arr[largest])    largest = right;if (largest != i) {    swap(arr[i], arr[largest]);    heapify(arr, largest, heap_size); // 注意：传的是 largest，不是 i+1}
}

排序阶段为什么每次把堆顶换到末尾后要 heap_size--
堆排序分两步：建堆 → 排序。排序阶段本质是不断取出最大值（堆顶），放到已排序区。这个“已排序区”就是数组末尾逐渐增长的后缀。

第一次交换 arr[0] 和 arr[n-1] 后，arr[n-1] 就是全局最大，不再参与堆调整
下次 heapify 只能作用于前 n-1 个元素，所以必须传入缩小后的 heap_size
漏写 heap_size-- 或写成 n--（影响后续循环边界）会导致重复排序、越界或逻辑混乱

典型错误配置：for (int i = n - 1; i > 0; i--) 循环中忘记在 swap 后调用 heapify(arr, 0, i)（注意是 i，不是 n）

C++ 实现里容易被忽略的细节
实际写的时候，这几个点常引发隐性 bug：

vector 传参建议用引用（vector&），避免建堆过程拷贝整块内存
建堆循环上限用 n / 2 - 1，不是 (n - 1) / 2——整数除法下二者在偶数 n 时相同，但奇数时后者可能多算一个节点
递归版 heapify 在极端情况（如升序数组建大根堆）可能导致栈溢出；生产环境建议改写为迭代版本
如果数据含重复值，堆排序不稳定——相同值的相对顺序可能改变，这点和 std::sort 默认行为一致，但得心里有数

最易被跳过的动作：建堆完成后，不验证前几个元素是否符合堆序（比如打印 arr[0] 是否为最大值），就直接进排序循环——结果错，还不知道错在哪一步。