堆排序的heapify必须从最后一个非叶子节点（下标n/2-1）开始自底向上调用，因为叶子节点无需调整，且正向从根开始会破坏已调整子树；heapify需比较当前节点与左右孩子（下标2i+1、2i+2），检查边界后交换并递归下沉。
堆排序的 heapify 不是“从上往下堆化”，而是从最后一个非叶子节点开始、自底向上逐个下沉——这点错，整个数组就建不出最大堆。
为什么必须从 last_non_leaf 开始倒着调用 heapify
数组表示完全二叉树时，下标从 0 开始，最后一个非叶子节点位置是 (n / 2) - 1（n 为数组长度）。叶子节点无需调整，因为它们没有子节点可比较；若从根（下标 0）开始正向 heapify，会导致子树已调整好的结构被父节点下沉破坏。
常见错误现象：heapify(arr, 0, n) 单独调用一次，结果数组不是最大堆——它只保证根满足堆性质，不保证左右子树已是堆。
正确做法：
立即学习“C++免费学习笔记（深入）”；
- 循环变量
i从n/2 - 1递减到 0 - 对每个
i调用heapify(arr, i, n) - 确保每次调用时，以
i为根的子树的左右子树都已是堆（由后续迭代保障）
heapify 函数里怎么选最大值并交换
heapify 的核心是“找当前节点与其左右孩子的最大值，若最大值不是自己，就交换，然后递归下沉”。注意三个关键点：
- 左孩子下标固定为
2 * i + 1，右孩子为2 * i + 2（0-indexed） - 必须先检查左孩子是否存在（
left ），再比右孩子；否则越界访问 - 找到最大值下标后，仅当它 ≠ 当前
i时才交换，并继续对那个孩子位置调用heapify
示例片段（关键逻辑）：
void heapify(vector<int>& arr, int i, int heap_size) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
<pre class='brush:php;toolbar:false;'>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<int>&），避免建堆过程拷贝整块内存 - 建堆循环上限用
n / 2 - 1，不是(n - 1) / 2——整数除法下二者在偶数n时相同，但奇数时后者可能多算一个节点 - 递归版
heapify在极端情况（如升序数组建大根堆）可能导致栈溢出；生产环境建议改写为迭代版本 - 如果数据含重复值，堆排序不稳定——相同值的相对顺序可能改变，这点和
std::sort默认行为一致，但得心里有数
最易被跳过的动作：建堆完成后，不验证前几个元素是否符合堆序（比如打印 arr[0] 是否为最大值），就直接进排序循环——结果错，还不知道错在哪一步。
