原地建大顶堆须从下标n/2-1开始自底向上调用heapify，因该位置是最后一个非叶子节点，确保子树先满足堆性质；若从0开始会破坏已调整结构。
原地建大顶堆的关键是自底向上调用 heapify
数组下标从 0 开始时，最后一个非叶子节点的下标是 n / 2 - 1（n 为数组长度）。不能从根（下标 0）开始向下调整，否则子树可能还没满足堆性质，导致结果错误。
正确做法是从 n / 2 - 1 往前遍历到 0，对每个节点执行一次 heapify（向下调整），确保以该节点为根的子树满足大顶堆定义。
-
heapify的作用：给定一个节点下标i和当前堆大小heap_size，比较i、左子（2*i + 1）、右子（2*i + 2），把最大值“沉”到i位置，若发生交换，则递归调整被换下去的那个子树 - 注意边界判断：左子或右子下标必须
，否则越界访问 - 建堆阶段时间复杂度是
O(n)，不是直觉上的O(n log n)，因为大部分节点在底层，高度小
heapify 函数怎么写才不出错
常见错误是子节点比较逻辑写反、越界没检查、交换后没继续向下调整。下面是一个安全、可直接复用的版本：
void heapify(vector<int>& nums, int heap_size, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
<pre class='brush:php;toolbar:false;'>if (left < heap_size && nums[left] > nums[largest])
largest = left;
if (right < heap_size && nums[right] > nums[largest])
largest = right;
if (largest != i) {
swap(nums[i], nums[largest]);
heapify(nums, heap_size, largest); // 必须递归！
}}
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
- 不要用循环代替递归（除非手动维护栈），容易漏掉某一层的调整
- 参数顺序建议固定为
(nums, heap_size, i)，和后续排序循环中heapify(nums, i, 0)的调用一致，避免传参颠倒 - 如果编译器不支持尾递归优化，且数据量极大（>1e6），可改用迭代版
heapify避免栈溢出
建堆后数组真的“是堆”吗？验证方法
建堆完成后，不能只靠肉眼观察首元素最大就认为成功。实际中容易忽略“局部满足≠全局满足”。推荐两种快速验证方式：
- 写个简单检查函数：遍历所有非叶子节点
i（即i < n/2），断言nums[i] >= nums[2*i+1]且（若存在）nums[i] >= nums[2*i+2] - 用小数组手算验证：比如
{3, 1, 4, 1, 5, 9, 2, 6}，建堆后应为{9, 5, 6, 1, 1, 4, 2, 3}（不唯一，但必须满足父子大小关系） - 调试时打印每轮
heapify后的数组，重点看下标n/2-1、n/2-2这几轮是否把较大数“托举”上来了
为什么建堆要从 n/2-1 开始而不是 0
下标从 0 开始的完全二叉树中，叶子节点集中在数组后半段，它们没有子节点，无需调整。第一个有子节点的节点，就是最后一个非叶子节点，其下标恰好是 n/2 - 1（整数除法向下取整）。
- 例如
n = 8，索引 0~7；8/2 - 1 = 3，即第 4 个元素（索引 3）是最后一个非叶子节点，它的子是索引 7 和 8（后者越界），所以只管左子 - 若从
0开始建堆，会反复破坏已调整好的子树结构，最终得到的不是合法堆 - 这个公式只适用于下标从 0 开始的数组；若代码里习惯用 1-based（如
A[1]开始存数据），则最后一个非叶子节点是n/2
真正容易被忽略的是：建堆只是堆排序的第一步，它不保证整个数组有序；而且 heapify 的递归终止条件、子节点索引计算、以及后续排序循环中 heap_size 的递减方式，三者必须严格配套——差一个等号或少一次 -1，整个排序就会错位或崩溃。
