堆排序的基石是建堆和向下调整：建堆必须从最后一个非叶子节点（下标为(n-1)/2）倒序开始，因叶子节点天然满足堆性质；向下调整需确保每次与左右孩子中较大者交换并持续下沉，且所有下标访问前必须边界检查。
最大堆的建堆和向下调整（heapify）是堆排序真正能跑起来的两个基石——没建好堆，后续全错；不理解 sift_down 的边界和索引逻辑，一调就越界或漏比较。
为什么从最后一个非叶子节点开始建堆？
因为叶子节点天然满足堆性质（没有子节点可破坏），只需从第一个可能有子节点的位置倒着处理。数组下标从 0 开始时，最后一个非叶子节点下标是 (n - 1) / 2（整除），不是 n / 2 - 1 —— 后者在 n=1 时会变成负数，而前者始终安全。
常见错误现象：std::out_of_range 或堆顶不是最大值，往往就是建堆起点错了，或者循环方向写成正向。
- 建堆必须从底向上，用
for (int i = n / 2 - 1; i >= 0; i--)是常见但危险的写法（n=0或n=1时未定义） - 更鲁棒的写法是
int last_non_leaf = (n > 0) ? (n - 1) / 2 : -1;，然后for (int i = last_non_leaf; i >= 0; i--) - 向下调整必须包含“当前节点与左右孩子中较大者交换”，且交换后要继续下沉——不能只换一次就停
sift_down 的三个关键边界条件
向下调整函数的核心不是“找最大值”，而是“把某个位置的值沉到它该在的地方”。它极易因下标计算出错而崩溃或逻辑错误。
假设当前节点下标为 i，左孩子是 2*i + 1，右孩子是 2*i + 2。所有比较和访问都必须先检查是否 。
- 必须先确认左孩子存在（
left ），再比大小；否则直接跳过 - 右孩子存在前提：先有左孩子，且
right ；否则只和左孩子比 - 交换后，
i要更新为较大孩子的下标，并继续循环——否则只做了一层调整
示例片段（精简版）：
void sift_down(vector<int>& heap, int i, int n) {
while (true) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
<pre class="brush:php;toolbar:false;"> if (left heap[largest]) largest = left;
if (right heap[largest]) largest = right;
if (largest == i) break;
swap(heap[i], heap[largest]);
i = largest;
}
}
建堆时间复杂度为什么是 O(n)，不是 O(n log n)？
直觉上每个 sift_down 最坏 O(log n)，n/2 个节点 → O(n log n)，但实际更优：越靠近底层的节点，下沉路径越短。数学推导得出总操作数上限是 2n，所以是线性。
这个结论影响实操判断：不要因为“建堆调了多次 sift_down”就怀疑性能——它本就不该成为瓶颈。但如果你在循环里反复建堆（比如每次插入都全量建），那才是真慢。
- 建堆适合批量初始化：已有全部数据，一次性构造
- 单点插入应走
sift_up（上浮），而非重建整个堆 -
std::make_heap就是标准库的建堆实现，行为一致；自己实现时别在建堆循环里加额外cout或日志——小数组看不出，大数据集会明显拖慢
最容易被忽略的是：向下调整函数的参数 n 表示当前有效堆长度，不是原始容器 size。堆排序过程中，每次把堆顶换到末尾后，n 要减一，下次 sift_down 只作用于前 n-1 个元素——漏掉这个，排序结果一定错。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
