堆排序核心是手动在数组上维护最大堆性质，分建堆（O(n)）和逐次取最大值排序（O(n log n)）两步，需正确计算下标、从最后一个非叶子节点开始建堆并缩小堆边界。
堆排序的核心是维护最大堆性质
堆排序不是靠调用现成的堆容器，而是手动在数组上模拟完全二叉树结构，通过反复调整使根节点始终为子树最大值。关键在于理解 heapify 过程：从最后一个非叶子节点开始向上 sift-down，确保以每个节点为根的子树满足最大堆（父 ≥ 左右子）。
常见错误是下标计算出错——C++ 数组从 0 开始，节点 i 的左子为 2*i+1，右子为 2*i+2，父节点为 (i-1)/2。漏掉这个偏移会导致越界或逻辑错乱。
分两步实现：建堆 + 逐个取出最大值
建堆阶段是 O(n)，不是直觉上的 n×log n，因为大部分节点在底层、调整代价小；排序阶段每次把堆顶（最大）与末尾交换，再对剩余 n-1 元素重新 heapify 根节点，共 n-1 次，每次 O(log n)。
- 建堆必须从最后一个非叶子节点开始，即
index = n/2 - 1（向下取整），不是从 0 或n-1 - 交换后要缩小堆边界（
heap_size--），否则会把已排好的最大值再次参与比较 -
heapify内部需递归或循环下滤，不能只比一次就停——可能需要一直沉到底
一个可直接运行的 C++ 实现示例
以下代码不依赖 STL 堆，纯数组操作，含注释说明关键位置：
立即学习“C++免费学习笔记（深入）”；
void heapify(std::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) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest); // 继续下滤
}}
void heapSort(std::vector<int>& arr) { int n = arr.size();
// 步骤1：建最大堆（从最后一个非叶子节点开始）
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// 步骤2：逐个取出堆顶，放至末尾
for (int i = n - 1; i > 0; i--) {
std::swap(arr[0], arr[i]); // 最大值移到已排序区
heapify(arr, i, 0); // 对剩余 i 个元素重新堆化
}}
容易被忽略的边界和性能细节
堆排序是原地、不稳定排序，heapify 的递归写法虽清晰但有栈开销；生产环境常用迭代版避免深递归。另外：std::make_heap 和 std::sort_heap 是标准库封装，但它们底层仍是同样逻辑，只是接口更简洁。
真正难调试的点往往在：n=0 或 n=1 时建堆循环是否跳过、right 下标是否越界、heapify 后未更新 largest 就继续用旧值比较——这些都会导致部分数据不参与排序或结果错乱。
