堆排序核心是heapify而非完整堆类实现，应优先使用std::make_heap和std::pop_heap原地排序，建堆O(n)，需从下标(n/2)-1开始sift_down，且不稳定、缓存不友好。
堆排序的核心是 heapify 而不是手写完整二叉堆类
多数人误以为堆排序必须先实现一个完整的 Heap 类（带 insert、extract_max 等），其实 C++ 标准库已提供底层支持，且原地排序只需关注 heapify 过程。关键在于：堆排序本质是「建堆 + 反复弹出最大值」，而建堆可以自底向上用 std::make_heap，或手动实现 sift_down 逻辑。
常见错误现象：std::make_heap 后直接遍历数组，发现顺序不对——因为它是最大堆，顶部是最大值，但整个数组不有序；必须配合 std::pop_heap 把最大值逐步移到末尾。
-
std::make_heap时间复杂度 O(n)，不是 O(n log n)；这是很多人忽略的优化点 - 若用
std::priority_queue实现，会额外分配内存，失去「原地」优势 - 手动实现
heapify时，最后一个非叶子节点下标是(n / 2) - 1，不是n / 2
用 std::make_heap 和 std::pop_heap 组合实现最简版本
这是最贴近算法导论描述、又避免重复造轮子的做法。它不引入额外容器，只操作原始数组，且可复用标准库的健壮性。
void heap_sort(std::vector& arr) { std::make_heap(arr.begin(), arr.end()); // 建最大堆 for (auto it = arr.end(); it != arr.begin(); --it) { std::pop_heap(arr.begin(), it); // 把堆顶移到 [it-1] } }
注意：std::pop_heap 不删除元素，只是把最大值换到当前范围末尾，然后调整剩余部分为堆。所以循环中 it 从 end() 开始递减，每次缩小堆的范围。
立即学习“C++免费学习笔记（深入）”；
- 如果传入
std::vector，需确保有随机访问迭代器（满足） - 排序后是升序；若要降序，改用
std::less作为第三个参数（默认是std::less，即最大堆 → 升序） - 对
int*数组也适用：std::make_heap(ptr, ptr + n)
手动实现 sift_down 时索引边界容易错
当不用标准库、必须手写时，核心是 sift_down 函数：从某节点出发，将其下沉到合适位置。最容易出错的是左右孩子索引计算和越界判断。
假设当前节点下标为 i，则：
- 左孩子：
2 * i + 1（不是2 * i，因数组从 0 开始） - 右孩子：
2 * i + 2 - 检查是否越界：必须同时满足
left 和right ，不能只比arr.size() - 下沉前要先比较左右孩子，选较大者再与父节点交换；否则可能破坏堆性质
建堆阶段必须从最后一个非叶子节点开始倒序调用 sift_down，否则无法保证整体堆结构。这个节点是 (arr.size() / 2) - 1，不是 arr.size() / 2 或 arr.size() - 1。
性能与稳定性：堆排序不适合小数组，也不稳定
堆排序时间复杂度稳定在 O(n log n)，但常数因子比快排大；实际中，STL 的 std::sort 通常用 introsort（快排+堆排兜底），而非纯堆排。
- 对少于 ~32 个元素的数组，插入排序更快；标准库实现通常会切分处理
- 堆排序不稳定：相等元素的相对位置可能改变，比如用于结构体排序时要注意字段相等性
- 缓存不友好：
sift_down的跳转访问模式导致 CPU cache miss 高于归并或快排
如果你真需要手写堆排序，优先考虑复用 std::make_heap + std::pop_heap；手动实现只在教学、嵌入式无 STL 或定制比较逻辑时才值得投入。
