堆排序核心是手动实现建堆和sift-down：下标从0开始时，节点i的左右子节点为2i+1、2i+2，父节点为(i-1)/2；建堆从最后一个非叶子节点n/2-1起向前调整。
堆排序的核心是维护最大堆性质
堆排序不是直接调用 std::make_heap，而是手动实现“自顶向下调整（sift-down）”和“建堆”两个关键过程。关键在于理解：数组下标从 0 开始时，节点 i 的左子节点是 2*i+1，右子节点是 2*i+2，父节点是 (i-1)/2（整除）。这和教材里下标从 1 开始的公式不同，写错这里会导致整个堆逻辑崩溃。
建堆必须从最后一个非叶子节点开始向前 sift-down，而不是从根或末尾开始——因为只有非叶子节点才可能破坏堆序。最后一个非叶子节点下标是 (n-2)/2（当 n>0），可简写为 n/2 - 1。
手写 siftDown 函数要注意边界和循环条件
这个函数负责把某个位置的元素“沉到底”，使其满足最大堆性质。常见错误是越界访问或漏判右子节点是否存在。
- 每次比较前先检查
left是否，否则直接跳出 - 只在
right 时才比较左右子节点取较大者 - 交换后要更新
root并继续下沉，不能只换一次就停 - 使用
std::swap(arr[i], arr[j])，避免手写交换逻辑出错
void siftDown(std::vector<int>& arr, int n, int i) {
while (true) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
<pre class="brush:php;toolbar:false;"> if (left arr[largest]) largest = left;
if (right arr[largest]) largest = right;
if (largest == i) break;
std::swap(arr[i], arr[largest]);
i = largest;
}
}
排序主流程分建堆和逐个取出两阶段
建堆阶段时间复杂度是 O(n)，不是 O(n log n)，这点常被误解；而排序阶段确实是 n 次 siftDown，每次最坏 O(log n)，总 O(n log n)。
取出元素时，把堆顶（最大值）和当前未排序区末尾交换，然后对新堆顶做 siftDown，堆大小减一。注意：siftDown 调用时传入的堆大小 n 是动态缩小的，不是原数组长度。
- 建堆：从
i = n/2 - 1递减到 0，对每个i调用siftDown(arr, n, i) - 排序：从
i = n-1递减到 1，swap(arr[0], arr[i])后调用siftDown(arr, i, 0) - 不要在循环里重复计算
2*i+1等表达式，编译器通常能优化，但可读性优先
测试时容易忽略的边界情况
空数组、单元素、已有序、逆序、含重复元素——这些都会暴露下标计算或循环终止条件的漏洞。
尤其注意当 n == 0 或 n == 1 时，建堆循环 for (int i = n/2 - 1; i >= 0; i--) 会因无符号整数溢出（如果 n 是 size_t）导致死循环。务必用有符号整型（如 int）作循环变量，或加 if (n 防御。
调试时可在 siftDown 入口加 assert(i >= 0 && i ，快速捕获非法调用。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
