堆排序核心是建堆与调整堆，需基于最大堆性质自底向上heapify并从n/2-1倒序build_heap，常见错误为下标越界、未递归下沉及范围参数错误。
堆排序的核心是建堆和调整堆
堆排序不是直接调用 std::make_heap 就完事——它依赖「最大堆」的结构性质：父节点值 ≥ 子节点值，且数组按层序存储。关键操作只有两个：heapify（自底向上调整单个子树）和 build_heap（从最后一个非叶子节点开始反复 heapify）。不理解这点，容易把下标算错或误以为要每次插入重建。
常见错误现象：std::out_of_range 或排序结果乱序，往往因为 heapify 中左右孩子下标越界没检查，或建堆时从 i = n/2 - 1 开始漏减 1。
- 数组索引从 0 开始时，节点
i的左孩子是2*i + 1，右孩子是2*i + 2，父节点是(i-1)/2 -
heapify必须递归或循环下沉，不能只比一次就停 - 建堆必须从最后一个非叶子节点倒序处理，即
i从n/2 - 1到0
手写 heapify 时最容易写错下标和终止条件
heapify 是堆排序里最常出 bug 的函数。它假设当前节点的左右子树已是最大堆，只需把当前节点“沉”到合适位置。问题常出在：没比较左右孩子谁更大、没更新 largest、下沉后忘了对新位置继续 heapify。
示例片段（C++，0-indexed）：
立即学习“C++免费学习笔记（深入）”；
void heapify(vector<int>& arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
<pre class='brush:php;toolbar:false;'>if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest); // 必须递归，不能省
}}
- 必须先判断
left < n和right < n，否则访问越界 - 两次
if是独立判断，不是else if——左右孩子都要比 - 递归调用参数是
largest，不是i；用循环替代递归也行，但需手动维护当前下标
排序主逻辑：先建堆，再逐个取最大值放末尾
建好最大堆后，堆顶 arr[0] 就是最大值。把它和末尾交换，再把剩余 n-1 个元素重新 heapify。这个过程重复 n-1 次，不需要额外空间。
注意：每次 heapify 的范围是 0 到 end（不包含 end），而 end 每轮减 1。很多人把 heapify 的 n 参数固定成原长度，导致后面部分堆结构被忽略。
- 第一轮：交换
arr[0]和arr[n-1]，然后heapify(arr, n-1, 0) - 第二轮：交换
arr[0]和arr[n-2]，然后heapify(arr, n-2, 0) - 循环变量
end应从n-1递减到1（不是0），共执行n-1次
用 std::make_heap 能省事，但要注意迭代器范围和稳定性
如果你只是想快速排序且不关心教学实现，std::make_heap + std::pop_heap 是标准库正解。但它默认构造最大堆，且 pop_heap 只把堆顶移到末尾，不自动缩短容器——你得手动 pop_back() 或控制迭代器范围。
常见误用：
- 写了
make_heap(v.begin(), v.end())，接着直接sort_heap(v.begin(), v.end())——这没问题，但中间不能插入或修改 - 想边 pop 边收集结果，却忘了
pop_heap后要v.pop_back()，否则下次pop_heap还会操作旧末尾 -
std::make_heap不稳定，相同元素的相对顺序可能改变；如需稳定，得自己实现或换算法
性能上，手写堆排序最坏 O(n log n)，常数略小；std::make_heap 实现通常优化充分，差别不大。但调试时，手写能看清每一步下沉路径，标准库则黑盒。
真正容易被忽略的是：堆排序不是稳定排序，而且原地排序意味着输入容器会被彻底重排——如果原始数据还需保留，得先 copy。
