最大堆调整（heapify）是从某非叶子节点出发向下比较交换以维护最大堆性质的过程，需从最后一个非叶子节点（索引n/2−1）开始逆序调用，时间复杂度O(log n)。
什么是堆排序中的最大堆调整（heapify）
堆排序的核心是维护一个最大堆：每个节点的值都不小于其子节点。所谓 heapify，就是从某个非叶子节点出发，向下比较并交换，确保以该节点为根的子树满足最大堆性质。它不是一次性建好整个堆，而是逐个“修复”局部结构。
关键点在于：只有当父节点违反堆序（即小于任一子节点）时才触发交换，并且交换后需递归检查被换下去的节点是否仍满足堆序——否则堆结构会断裂。
-
heapify的时间复杂度是O(log n)，因为最多下沉到叶子层 - 必须从最后一个非叶子节点开始向上调用，即从索引
(n / 2) - 1开始（数组下标从 0 起） - 左子节点索引是
2 * i + 1，右子节点是2 * i + 2，父节点是(i - 1) / 2
如何手写 C++ 版本的 heapify 函数
标准库没有暴露底层 heapify 接口，std::make_heap 内部虽用类似逻辑，但不可见。要理解原理或定制行为（比如支持自定义比较器、调试堆状态），必须自己实现。
下面是最简可用的递归版 heapify，适用于 vector<int></int> 或原生数组：
立即学习“C++免费学习笔记（深入）”；
void heapify(vector<int>& arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
<pre class='brush:php;toolbar:false;'>if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest); // 继续下沉
}}
注意：n 是当前考虑的堆大小（可能小于容器总长），i 是起始下标。若用于排序，后续还要做「堆顶弹出 + 末尾补位 + 再次 heapify」两步循环。
构建初始最大堆的常见错误
新手常犯的错是正向遍历所有元素调用 heapify，或者从下标 0 开始向下调整——这会导致部分子树从未被检查，堆结构不成立。
正确做法只处理非叶子节点，且必须**从后往前**：
- 叶子节点无需调整（它们没有子节点）
- 最后一个非叶子节点索引 =
arr.size() / 2 - 1（整数除法） - 若用
for (int i = n/2 - 1; i >= 0; i--)，别漏掉i == 0 - 若用
size_t类型循环变量，i >= 0永真，会导致无限循环——务必用有符号类型如int
构建代码示例：
void buildMaxHeap(vector<int>& arr) {
int n = arr.size();
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
}堆排序完整流程与性能陷阱
堆排序分两阶段：建堆（O(n)） + 反复取最大值并重堆（O(n log n)）。虽然理论稳定，但实际中 cache 不友好、非稳定排序、常数因子大，所以一般不用它替代 std::sort。
真正需要注意的是边界细节：
- 每次把堆顶
arr[0]和末尾arr[i]交换后，新堆大小变为i（不是i-1），所以下次heapify(arr, i, 0) - 循环应从
int i = n - 1降到1（不是0），因为单元素天然有序 - 如果数据含重复值，堆排序不稳定——相同值的相对位置可能改变，这点和
std::stable_sort本质不同
最后一句提醒：如果你只是想排个数组，直接用 std::make_heap + std::sort_heap 更安全；只有当你需要观察堆中间状态、或嵌入实时数据流做动态堆管理时，才值得手动实现 heapify。
