heapify 必须从最后一个非叶子节点开始，因为只有非叶子节点可能破坏堆序，且自底向上调整可确保每次 siftDown 时左右子树已是合法子堆；其下标为 n//2−1（0-indexed）。
为什么 heapify 必须从最后一个非叶子节点开始？
因为堆的结构性质决定了：只有非叶子节点才可能破坏堆序，而自底向上调整才能保证每次调用 siftDown 时，其左右子树已是合法子堆。若从根开始或从任意位置乱序调整，子树未就绪会导致结果错误。
最后一个非叶子节点下标是 (n / 2) - 1（0-indexed 数组），这个公式来自完全二叉树性质——第 i 个节点的左子为 2*i + 1，右子为 2*i + 2；当 2*i + 1 >= n 时即无左子，也就是叶子节点。解得 i ，最大整数索引就是 <code>n/2 - 1。
常见错误：
- 写成
n/2或(n-1)/2—— 在偶数长度时会越界或漏调一个父节点 - 遍历方向用正向（
i = 0到n/2-1）—— 子树未建好，siftDown无效
siftDown 的终止条件和交换逻辑怎么写才不出错？
核心是：只要当前节点比某个子节点小，就要和「较大子节点」交换，并继续下沉；一旦它不小于两个子节点，就停。
立即学习“C++免费学习笔记（深入）”；
实操要点：
- 先算左右子下标：
left = 2 * i + 1，right = 2 * i + 2 - 只在
left 时才进入循环（因为没有左子就一定没有右子） - 用
largest = i初始化，再分别比较 left/right，更新largest；不要用 if-else 嵌套判断谁更大，容易漏情况 - 交换后必须更新
i = largest，否则死循环
示例关键片段：
void siftDown(vector<int>& heap, int i, int n) {
while (true) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < n && heap[left] > heap[largest]) largest = left;
if (right < n && heap[right] > heap[largest]) largest = right;
if (largest == i) break;
swap(heap[i], heap[largest]);
i = largest;
}
}
建堆时间复杂度真的是 O(n)？为什么不是 O(n log n)？
直觉上每个 siftDown 最坏 O(log n)，共约 n/2 次调用，看似 O(n log n)，但实际是 O(n)。原因在于：越靠近底层的节点，下沉路径越短。数学上可证，所有节点的下沉总步数上限是 2n。
影响实操的点：
- 别为了“优化”把建堆拆成 n 次
push（即逐个插入），那是 O(n log n)，且额外分配空间 - 如果数据动态到达，才用插入式建堆；静态数组必须用自底向上
heapify - 某些 STL 实现（如
std::make_heap）正是基于此 O(n) 算法，直接信任它
用原生数组实现时，下标从 0 还是 1 开始？
现代 C++ 通用做法是 0-indexed。虽然教科书常用 1-indexed（父子关系更对称：i → 2i, 2i+1），但实际编码中 0-indexed 更自然，且 std::vector、std::make_heap 全部采用它。
对应关系必须统一：
- 父节点：
(i - 1) / 2（不是i / 2） - 左子：
2 * i + 1（不是2 * i） - 右子：
2 * i + 2（不是2 * i + 1） - 最后一个非叶子节点：
n / 2 - 1（整除，向下取整）
混用 0/1 起始下标是调试时最隐蔽的 bug 来源之一，尤其在手写测试用例时容易手动算错索引。
真正难的不是写对一次，而是让 siftDown、建堆循环、后续排序交换三处下标逻辑完全咬合——少一个 +1 或多一个 -1，堆就悄无声息地失效了。
