堆排序核心是手动在数组上维护最大堆性质，分建堆（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 堆，纯数组操作，含注释说明关键位置：
void heapify(std::vector& arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left zuojiankuohaophpcn n && arr[left] youjiankuohaophpcn arr[largest]) largest = left; if (right zuojiankuohaophpcn n && arr[right] youjiankuohaophpcn arr[largest]) largest = right; if (largest != i) { std::swap(arr[i], arr[largest]); heapify(arr, n, largest); // 继续下滤 }}
void heapSort(std::vector
& arr) { int n = arr.size(); // 步骤1：建最大堆（从最后一个非叶子节点开始） for (int i = n / 2 - 1; i youjiankuohaophpcn= 0; i--) heapify(arr, n, i); // 步骤2：逐个取出堆顶，放至末尾 for (int i = n - 1; i youjiankuohaophpcn 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就继续用旧值比较——这些都会导致部分数据不参与排序或结果错乱。
