二叉堆的构建与批量建堆（Heapify）详解

一、问题背景

二叉堆是一种常用的完全二叉树结构，通常用于实现优先队列。它满足以下性质：

• 在最大堆中，每个节点的值都大于或等于其子节点的值（最小堆则相反）。
• 堆可以用数组紧凑存储，节点 i 的父节点为 (i-1)/2，左子节点为 2*i+1，右子节点为 2*i+2。

当我们从一个无序数组构建堆时，有两种常见方法：

1. 逐个插入法（自顶向下）
2. 批量建堆法（自底向上，也叫 heapify 或建堆算法）

批量建堆的时间复杂度为 O(n)，优于逐个插入的 O(n log n)，是理解堆操作的核心知识点之一。

二、逐个插入法回顾

假设初始数组为空，依次插入 n 个元素：

• 每次插入时，将新元素放在数组末尾，然后上浮（sift-up）调整位置，恢复堆性质。
• 上浮操作最多需要 O(log n) 时间，总时间为 O(n log n)。

这种方法简单直观，但效率不高，因为大部分元素是较小的（在最大堆中），实际上浮次数较少，但仍无法达到线性时间。

三、批量建堆（Heapify）的直观理解

给定一个长度为 n 的数组，将其视为完全二叉树，但可能不满足堆性质。
批量建堆的核心思想：从最后一个非叶子节点开始，向前逐个进行“下沉”操作，使每个子树都成为堆。

为什么从最后一个非叶子节点开始？

• 叶子节点没有子节点，本身已经是一个合法的堆（无需调整）。
• 最后一个非叶子节点的下标是 floor(n/2)-1（0-based 索引）。

步骤分解：
假设数组为 [3, 8, 2, 1, 7, 6, 4, 5]，n=8。

1. 最后一个非叶子节点下标 = floor(8/2)-1 = 3（值为 1）。
2. 从下标 3 开始，向前到下标 0，依次对每个节点执行下沉（sift-down）操作。
   • 下沉操作：将当前节点与两个子节点比较，若不满足堆性质，则与较大的子节点交换（最大堆），并继续向下调整。

四、下沉操作（sift-down）的详细过程

以最大堆为例，对节点 i 进行下沉：

1. 找到 i 的左子节点 left = 2i+1，右子节点 right = 2i+2。
2. 设 largest = i。
3. 如果 left < n 且 array[left] > array[largest]，则 largest = left。
4. 如果 right < n 且 array[right] > array[largest]，则 largest = right。
5. 如果 largest ≠ i，交换 array[i] 和 array[largest]，然后令 i = largest，重复步骤 1~5（递归或循环）。

示例：对 [3, 8, 2, 1, 7, 6, 4, 5] 的下标 1（值为 8）下沉：

• 左子节点为下标 3（值 1），右子节点为下标 4（值 7）。
• largest 是当前节点 8（因为 8 > 1 且 8 > 7），无需交换，结束。

五、完整批量建堆示例

数组：[3, 8, 2, 1, 7, 6, 4, 5]，n=8。
最后一个非叶子节点下标依次为：3, 2, 1, 0。

1. i=3（值 1）：左子为下标 7（值 5），右子不存在。largest=7，交换 1 和 5 → [3, 8, 2, 5, 7, 6, 4, 1]。
2. i=2（值 2）：左子为下标 5（值 6），右子为下标 6（值 4）。largest=5，交换 2 和 6 → [3, 8, 6, 5, 7, 2, 4, 1]。
3. i=1（值 8）：左子 5，右子 7，8 最大，无需交换。
4. i=0（值 3）：左子 8，右子 6，largest=1，交换 3 和 8 → [8, 3, 6, 5, 7, 2, 4, 1]。
   然后对新的 i=1（值 3）继续下沉：左子 5，右子 7，largest=4，交换 3 和 7 → [8, 7, 6, 5, 3, 2, 4, 1]。
   对新的 i=4（值 3）下沉：左子下标 9 不存在，结束。

最终得到最大堆：[8, 7, 6, 5, 3, 2, 4, 1]。
验证：父节点均大于等于子节点。

六、时间复杂度分析 O(n) 的推导

直观上似乎每个节点下沉 O(log n)，n 个节点应该是 O(n log n)，但实际是 O(n)。

精确分析：

• 完全二叉树高度 h = floor(log₂ n)。
• 高度为 h 的节点最多有 ceil(n/2^(h+1)) 个。
• 一个高度为 h 的节点下沉最多比较 2h 次（每次与子节点比较两次）。

总比较次数 T(n) ≤ Σ_{h=0}^{log n} (n/2^{h+1}) * 2h
= n * Σ_{h=0}^{log n} h/2^h

已知 Σ_{h=0}^{∞} h/2^h = 2（收敛级数），所以 T(n) ≤ 2n = O(n)。

七、代码实现（Python）

def heapify(arr):
    n = len(arr)
    # 从最后一个非叶子节点开始向前遍历
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)

def sift_down(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        sift_down(arr, n, largest)  # 递归向下调整

# 测试
arr = [3, 8, 2, 1, 7, 6, 4, 5]
heapify(arr)
print(arr)  # 输出最大堆数组

八、常见应用场景

1. 堆排序的第一步：用 heapify 在 O(n) 时间建堆，然后逐个弹出堆顶。
2. 优先队列的批量初始化。
3. 在流式数据中动态维护 Top-K 元素时，可定期重新 heapify 优化结构。

九、小结

批量建堆（heapify）通过自底向上的下沉操作，在 O(n) 时间内将无序数组转化为堆。
关键点：

• 从最后一个非叶子节点开始向前处理。
• 每个节点的下沉操作复杂度与其高度成正比。
• 总复杂度为线性，优于逐个插入的 O(n log n)。