最大堆是父节点值≥子节点值的完全二叉树，用数组按层序存储；不能直接排序构建，须通过heapify自底向上调整，从最后一个非叶子节点（下标n/2−1）开始sift_down，确保每个子树满足堆序性质。
什么是最大堆，以及为什么不能直接用数组“构建”
最大堆不是靠把数组排序得到的，而是通过调整数组元素位置，让每个父节点都大于等于其子节点。关键在于“堆化”（heapify）过程——它不改变数组长度，只重排元素索引关系。常见误解是以为 std::make_heap 会返回新结构，其实它就地修改原数组，且依赖随机访问迭代器和可比较类型。
用 std::make_heap 快速建堆的注意事项
这是最直接的方式，但容易出错的点集中在比较器、迭代器范围和元素类型上：
-
std::make_heap默认使用std::less<t></t>，即构建最大堆；若传入std::greater<t></t>，反而建成最小堆 - 迭代器范围必须有效：对数组
int arr[5]，应传arr和arr + 5，而非&arr[0]和&arr[5]（后者虽等价，但易混淆指针算术） - 元素必须支持
operator，或显式提供比较函数对象；自定义类需确保比较逻辑满足严格弱序 - 建堆时间复杂度是 O(n)，不是 O(n log n)，因为大部分节点在底层，无需下沉很深
int arr[] = {3, 1, 4, 1, 5};
std::make_heap(std::begin(arr), std::end(arr)); // 原地变最大堆：{5, 3, 4, 1, 1}
手动实现 sift_down 的核心逻辑
理解 std::make_heap 背后怎么做，关键是写对下沉函数。最大堆中，从最后一个非叶子节点开始向前 heapify：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 数组下标从 0 开始时，下标为
i的节点，左子为2*i+1，右子为2*i+2 - 下沉时先找左右子中较大者，再与当前节点比较；仅当子更大才交换，并继续下沉到该子树
- 边界检查必须做：左子下标
才存在，右子还需额外判断 <code> - 别漏掉“当前节点已比两子都大”的终止条件，否则无限循环
void sift_down(int arr[], int i, int size) {
while (true) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left arr[largest]) largest = left;
if (right arr[largest]) largest = right;
if (largest == i) break;
std::swap(arr[i], arr[largest]);
i = largest;
}
}
建堆后怎么保持堆性质？别忘了 std::push_heap 和 std::pop_heap
数组建好最大堆只是起点。后续插入或删除必须用配套操作，否则破坏结构：
-
std::push_heap要求：新元素已放在末尾，再调用它上浮；顺序反了（先调用再放值）会导致未定义行为 -
std::pop_heap不删除元素，只是把堆顶换到末尾并重新堆化剩余部分；真删要用.pop_back()配合 - 所有这些算法都要求容器支持随机访问且元素可移动；
std::vector安全，std::list不行 - 如果频繁增删，考虑用
std::priority_queue<int std::vector>, std::less<int>></int></int>封装，避免手写边界
真正难的不是第一次建堆，而是后续维护时忘记“堆不是有序数组”——堆顶最大，其余无序。打印整个数组看不出规律，是正常现象。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
