1. 概述
堆（Heap） 是一种特殊的完全二叉树结构，常用于构建优先队列。堆有两个重要变种：最大堆（Max-Heap） 和 最小堆（Min-Heap）。
本文重点讲解 Max-Heapify 操作，即如何将一个不符合最大堆特性的二叉树调整为最大堆，并通过示例帮助理解其工作原理。
2. 堆的定义
堆是一种完全二叉树结构，具有堆性质（Heap Property）：
- 最大堆（Max-Heap）：任意父节点的值都 大于等于 其子节点的值。根节点是整个堆中最大的值。
- 最小堆（Min-Heap）：任意父节点的值都 小于等于 其子节点的值。根节点是整个堆中最小的值。
来看两个示例：
- 第一棵树是最大堆：根节点值最大，每个父节点都大于其子节点。
- 第二棵树是最小堆：根节点值最小，每个父节点都小于其子节点。
3. Max-Heapify 操作
3.1 算法逻辑
Max-Heapify 的目标是将一个节点及其子树调整为最大堆结构。该操作是构建最大堆的基础步骤之一。
以下是 Max-Heapify 的伪代码：
algorithm MaxHeapify(B, s):
// B 是数组，s 是当前节点索引
left <- 2 * s
right <- 2 * s + 1
if left <= B.length and B[left] > B[s]:
largest <- left
else:
largest <- s
if right <= B.length and B[right] > B[largest]:
largest <- right
if largest != s:
swap(B[s], B[largest])
MaxHeapify(B, largest)
3.2 核心步骤说明
left和right是当前节点的左右子节点索引。- 比较当前节点与其子节点，找出最大值。
- 如果最大值不是当前节点，则交换位置，并递归调用 MaxHeapify，继续调整子树。
3.3 构建最大堆
从最后一个非叶子节点开始，依次对每个节点调用 MaxHeapify：
algorithm MaxHeapBuilding(B):
// B 是输入数组
n <- length(B)
B.heapsize <- n
for k <- n / 2, n / 2 - 1, ..., 1:
MaxHeapify(B, k)
4. Max-Heapify 示例
我们以数组 B = [10, 20, 25, 6, 12, 15, 4, 16] 为例，演示如何通过 Max-Heapify 构建最大堆。
4.1 初始二叉树结构
4.2 从最底层子树开始检查
该子树不符合最大堆特性，需交换父子节点值。
4.3 继续向上调整
依次检查并调整所有子树：
- 符合条件的无需调整 ❌
- 不符合条件的交换并递归调整 ✅
最终结果如下图所示：
此时整棵树已满足最大堆特性。
5. 总结
- Max-Heapify 是构建最大堆的核心操作。
- 从最后一个非叶子节点开始，逐层向上调整。
- 每次调整后，递归处理受影响的子树。
- 时间复杂度为 **O(log n)**，构建整个堆的时间复杂度为 **O(n)**。
掌握 Max-Heapify 是理解堆排序、优先队列等高级算法的基础，建议多动手画图、调试代码以加深理解。