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

1. 知识背景与问题描述
二叉堆（Binary Heap）是一种特殊的完全二叉树，满足堆序性质：在最小堆中，每个节点的值都不大于其子节点的值；在最大堆中，每个节点的值都不小于其子节点的值。堆是实现优先队列的经典数据结构。
一个常见的基础操作是堆的构建，即给定一个无序数组，如何高效地将其调整为一个满足堆序性质的堆。最直观的方法是从空堆开始，不断调用插入（insert）操作，每次插入时间复杂度为O(log n)，总时间为O(n log n)。然而，存在一种更优的批量建堆（Heapify） 算法，其时间复杂度可达O(n)。本专题将详细讲解这个算法的原理、步骤、复杂度分析和实现细节。

2. 核心思想：自底向上（Bottom-up）的下沉（Sink）
批量建堆算法的核心思想是**“从最后一个非叶子节点开始，向前遍历每个节点，并对每个节点执行下沉（Sink，或称为堆化-Heapify）操作，直到根节点”**。

• 为什么从最后一个非叶子节点开始？ 因为叶子节点（只占约一半节点）没有子节点，自身天然满足堆序性质，无需处理。
• 为什么是“自底向上”？ 通过从下往上的顺序，当我们处理某个节点时，它的两个子树都已经是通过下沉操作调整好的、独立的、满足堆序的子堆。此时，只需要确保这个节点满足堆序性质（可能需要与子节点交换并递归下沉），就能保证以这个节点为根的子树也成为一个合法的堆。
• 下沉（Sink）操作：以最大堆为例，比较当前节点与其左右子节点的值。如果当前节点小于其某个子节点，则将其与较大的那个子节点交换位置。交换后，原节点移动到了子节点位置，可能再次破坏该子树的堆序，因此需要在该位置递归地进行相同的下沉操作，直到当前节点不小于其任何子节点，或者到达了叶子节点。

3. 算法流程与步骤拆解（以构建最大堆为例）
假设给定一个长度为n的数组arr，索引从0开始。
步骤1：定位最后一个非叶子节点的索引。
在完全二叉树中，对于索引为i的节点：

• 其左子节点索引为 2*i + 1
• 其右子节点索引为 2*i + 2
• 其父节点索引为 floor((i-1)/2)
  最后一个节点的索引是 n-1，其父节点就是最后一个非叶子节点，索引为 parent_idx = floor((n-1)-1)/2) = floor(n/2) - 1。

步骤2：自底向上遍历并下沉。
从索引 start_idx = floor(n/2) - 1 开始，递减循环直到根节点（索引0）。对于每个索引i，调用 sink(arr, i, n) 函数。
sink(arr, i, n) 函数伪代码：

函数 sink(arr, i, n):
    largest = i        // 假设当前节点i是最大值
    left = 2*i + 1
    right = 2*i + 2

    // 如果左子节点存在且大于当前最大值候选
    if left < n 且 arr[left] > arr[largest]:
        largest = left
    // 如果右子节点存在且大于当前最大值候选
    if right < n 且 arr[right] > arr[largest]:
        largest = right

    // 如果最大值不是当前节点i，说明堆序被破坏，需要交换并继续下沉
    if largest != i:
        交换 arr[i] 和 arr[largest]
        // 递归地对新的位置（largest）进行下沉
        sink(arr, largest, n)

举例：无序数组 [3, 9, 2, 1, 4, 5]，n=6。

• 最后一个非叶子节点索引 = floor(6/2)-1 = 2。从索引2开始。
• i=2: 节点值2，左子5>2，交换。数组变 [3, 9, 5, 1, 4, 2]。对新的索引2（值2）判断，它是叶子节点，停止。
• i=1: 节点值9，左子1<9，右子4<9，满足堆序，无需操作。
• i=0: 节点值3，左子9>3，右子5<9，最大值是左子9，交换。数组变 [9, 3, 5, 1, 4, 2]。对新的索引1（值3）递归：其左子1<3，右子4>3，交换。数组变 [9, 4, 5, 1, 3, 2]。对新的索引4（值3）判断，它是叶子节点，停止。
  最终得到最大堆数组：[9, 4, 5, 1, 3, 2]，对应树为：根9，左子4（子节点1,3），右子5（子节点2）。

4. 时间复杂度分析 O(n)
直观上，有大约n/2个节点（叶子）无需操作，n/4个节点可能下沉1层，n/8个节点可能下沉2层，以此类推。
总操作次数 T(n) = Σ (从高度h=0到H) [ (n / 2^{h+1}) * h ]。这是一个等差-等比数列求和。
经过推导（详细数学证明略），其上限为 c * n，其中c是一个常数（小于2）。因此，批量建堆的时间复杂度是O(n)。这比n次连续插入的O(n log n)要快。

5. 代码实现（Python示例）

def heapify(arr):
    """将无序数组arr原地转换为最大堆"""
    n = len(arr)
    # 从最后一个非叶子节点开始，向前遍历
    start_idx = n // 2 - 1
    for i in range(start_idx, -1, -1):
        _sink(arr, i, n)

def _sink(arr, i, 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]  # 交换
        _sink(arr, largest, n)  # 递归调整

# 示例
if __name__ == "__main__":
    data = [3, 9, 2, 1, 4, 5]
    print("原始数组:", data)
    heapify(data)
    print("堆化后数组 (最大堆):", data)
    # 输出: [9, 4, 5, 1, 3, 2]

6. 总结与应用

• 批量建堆（Heapify） 利用自底向上的下沉操作，能在O(n)时间内将无序数组构造成堆。
• 关键点在于：从最后一个非叶子节点开始，确保每个子树都被正确堆化。
• 这是许多堆相关算法（如堆排序、Top-K问题的堆解法）的基础步骤，其高效性使得“构建优先队列”的开销远低于想象。
• 对于动态插入的场景，仍需使用标准的O(log n)的插入操作（上浮-Swim）。Heapify主要用于初始批量数据的快速构建。