C / C++ / 系统课时
最大堆需要满足什么规则
最大堆需要满足什么规则
最大堆不是“整个数组从大到小排序”,而是一棵满足局部父子约束的完全二叉树:每个父节点都不小于自己的孩子。正是这个局部规则,让最大值稳定停在根节点,同时保留高效插入和删除所需的结构空间。
学习目标
- 说明最大堆同时满足的结构性质与顺序性质
- 区分“父节点不小于孩子”与“数组整体有序”
- 能用数组下标检查一个序列是否满足最大堆规则
最大堆有两条规则
最大堆必须同时满足两个条件。首先,它在形状上是完全二叉树,因此可以紧凑存进数组。其次,对任意存在孩子的节点,父节点的值必须大于或等于左、右孩子的值。

例如数组 [90, 70, 80, 20, 40, 60, 50] 是合法最大堆。90 大于 70 和 80,70 大于 20 和 40,80 大于 60 和 50。因此根节点一定是整个堆的最大值。
为什么数组不必整体有序
最大堆只比较“父与直接孩子”,并不要求兄弟节点之间有固定顺序,也不要求不同子树之间整体有序。上面的数组中,70 出现在 80 前面,依然完全合法。
这也是堆和排序数组的根本区别:排序数组为了保持全局顺序,插入中间位置可能需要移动大量元素;堆只维护局部关系,插入新元素后沿父节点方向调整即可。
用程序检查最大堆
对 0 起始数组,只需要检查每个非根节点 i 是否满足 heap[(i - 1) / 2] >= heap[i]。一旦出现孩子大于父节点,就违反最大堆规则。
c
#include <stdio.h>
#include <stdbool.h>
bool is_max_heap(const int heap[], int n) {
for (int i = 1; i < n; ++i) {
int parent = (i - 1) / 2;
if (heap[parent] < heap[i]) {
return false;
}
}
return true;
}
int main(void) {
int valid[] = {90, 70, 80, 20, 40, 60, 50};
int invalid[] = {90, 70, 95, 20, 40, 60, 50};
int n1 = (int)(sizeof(valid) / sizeof(valid[0]));
int n2 = (int)(sizeof(invalid) / sizeof(invalid[0]));
printf("valid: %s\n", is_max_heap(valid, n1) ? "yes" : "no");
printf("invalid: %s\n", is_max_heap(invalid, n2) ? "yes" : "no");
return 0;
}预期输出
text
valid: yes
invalid: no第二个数组中,下标 2 的值是 95,其父节点下标为 0,值为 90。因为 95 > 90,孩子反而大于父节点,所以它不是最大堆。
判断时最容易混淆的点
最大堆允许父子相等,因此规则是“不小于”,不是“严格大于”。叶子节点没有孩子,自然不需要继续检查。空数组或只有一个元素的数组也不会违反父子关系,通常可视为合法堆。
真正需要记住的是:完全二叉树决定存储形状,父节点不小于孩子决定最大值的位置。这两条规则共同成立,才叫最大堆;仅仅“根节点最大”还不够。
按自己的节奏,确认真正理解。