堆排序核心是建堆与反复弹顶，需严格按0起始下标计算父子关系，升序建最大堆，降序建最小堆，heapify自底向上调整，避免下标错误导致静默失败。
堆排序的核心其实是“建堆 + 反复弹顶”
堆排序不是靠写一堆比较逻辑硬排，而是把数组看成一棵完全二叉树，先让它满足堆性质（最大堆或最小堆），再每次把堆顶（最大/最小元素）和末尾交换，缩容后重新调整堆。关键不在“排序”，而在“维护堆结构”。
常见错误现象：std::out_of_range 或结果乱序，往往是因为下标算错——C++ 数组从 0 开始，但父子节点关系必须严格按 parent = (i-1)/2、left = 2*i+1、right = 2*i+2 算，不能套用教材里从 1 开始的公式。
- 建堆阶段用
heapify自底向上调整，别从根开始——那样会漏掉子树 - 排序阶段每次
swap(arr[0], arr[end])后，只对[0, end-1]范围调用heapify，否则堆结构被破坏 - 如果要升序，建最大堆；降序则建最小堆——别反了，否则每轮弹出的是最小值却往末尾塞，顺序就崩了
手写 heapify 时最容易错的三个下标边界
heapify 是堆排序的心脏，它保证以某节点为根的子树满足堆性质。错一个下标，整个排序就静默失败——不报错，但结果不对。
典型错误：在判断 right 存在时写成 right 却忘了 <code>left 可能已经越界，导致访问非法内存；或者在递归调用时传入了错误的 largest 下标，让调整跑偏。
立即学习“C++免费学习笔记（深入）”；
- 必须先检查
left ，再用 <code>left算right，否则right可能是负数或溢出 - 找到最大值下标
largest后，仅当largest != i才交换并递归——避免空递归和栈溢出 - 递归调用
heapify(arr, largest, size)，不是heapify(arr, i, size)，否则永远卡在原地
示例片段（升序）：
void heapify(vector<int>& arr, int i, int size) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < size && arr[left] > arr[largest]) largest = left;
if (right < size && arr[right] > arr[largest]) largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, largest, size); // 注意这里传 largest，不是 i
}
}
为什么不用 std::make_heap 而要自己写？
标准库的 std::make_heap + std::pop_heap 确实能一行建堆、一行弹顶，但实际项目里经常绕不开两个现实问题：一是需要控制比较逻辑（比如按结构体字段排），二是调试时根本看不到中间堆状态。
用标准库时，std::pop_heap 只把最大值移到末尾，但不自动缩容——你得手动 pop_back()，否则下次 pop_heap 还会把它当候选；而自己写能一眼看清 end 指针怎么移、堆范围怎么缩。
-
std::make_heap默认建最大堆，升序要用它；但若想升序却误传greater<int>()，反而建出最小堆，结果全反 - 标准库函数操作的是迭代器区间，
pop_heap后容器大小不变，容易误以为“已删”，导致后续逻辑读到脏数据 - 自定义类型排序时，
std::make_heap要求重载operator<或传Compare，而手写heapify可直接内联比较逻辑，更直观
性能和稳定性：堆排序真比快排慢吗？
平均时间复杂度都是 O(n log n)，但堆排序的常数项更大——每次 heapify 都可能触发多次比较+交换，且缓存不友好（跳着访问数组）。不过它胜在稳定：最坏也是 O(n log n)，不像快排可能退化到 O(n²)。
真正影响实测速度的，往往不是算法本身，而是是否做了基础优化：
- 把
heapify写成非递归（用 while 循环代替递归），避免函数调用开销和栈深度限制 - 建堆阶段从最后一个非叶子节点开始（
size/2 - 1），而不是从 0 开始——省掉一半无效尝试 - 如果数据基本有序，堆排序不会受益，此时
std::sort（通常是混合快排）大概率更快；但若内存受限、又需确定性最坏性能，堆排序仍是合理选择
最后提醒一句：堆排序的“原地”是有代价的——它破坏原始顺序且不可逆，调试时别直接拿线上数据试，先拷一份。
