Hello 算法：建堆操作的两种实现与 O(n) 时间复杂度的严格推导

建堆（build heap）指用一个列表的全部元素一次性构建出满足堆性质（完全二叉树 + 每个节点不小于/不大于其子节点）的堆。本文基于《Hello 算法》"堆"一章中的建堆章节（build_heap.md），完整讲解两种建堆方法——"借助入堆操作"（$O(n \log n)$）与"倒序遍历 + 从顶至底堆化"（$O(n)$），并结合仓库中 Python、Java、C++、Rust 等语言的 MaxHeap 构造方法源码，逐行验证实现细节，最后通过完美二叉树的等比数列求和，严格推导出高效建堆 $O(n)$ 时间复杂度的数学依据。读完后，你将能够理解为什么"逐个入堆"不是最优建堆方式，并能独立在任意语言中写出 O(n) 的建堆代码。

为什么需要"建堆"操作

在《Hello 算法》的堆一章中，元素入堆 push() 与堆顶元素出堆 pop() 的时间复杂度均为 $O(\log n)$（见 heap.md 中的操作效率表）。但在实际场景中，我们往往不是从零开始逐个插入元素，而是已经持有整个列表，希望直接把它变成一个合法的堆。这个"从列表到堆"的过程就是建堆操作，它也是优先队列批量初始化、堆排序、Top K 等经典算法的基础步骤。

方法一：借助入堆操作实现（$O(n \log n)$）

最直觉的做法是复用已有的入堆逻辑：

1. 创建一个空堆；
2. 遍历列表，依次将每个元素"入堆"——先将元素追加到堆的尾部，再对该元素执行"从底至顶堆化"（sift_up）。

每当一个元素入堆，堆的长度加一。由于完全二叉树的节点是从顶到底依次被添加的，因此堆是**"自上而下"构建**的。

在 my_heap.py 中，这一逻辑由 push() 与 sift_up() 两个方法承载：

def push(self, val: int):
    """元素入堆"""
    # 添加节点
    self.max_heap.append(val)
    # 从底至顶堆化
    self.sift_up(self.size() - 1)

def sift_up(self, i: int):
    """从节点 i 开始，从底至顶堆化"""
    while True:
        p = self.parent(i)
        # 当"越过根节点"或"节点无须修复"时，结束堆化
        if p < 0 or self.max_heap[i] <= self.max_heap[p]:
            break
        self.swap(i, p)
        i = p

push() 的每次调用都要把新元素沿树"上顶"，最多上顶到根节点，循环轮数等于树高 $O(\log n)$。设元素数量为 $n$，每个元素入堆均摊 $O(\log n)$，因此该方法的整体时间复杂度为 $O(n \log n)$。

方法二：倒序遍历 + 从顶至底堆化（$O(n)$）

《Hello 算法》给出了一种更高效的建堆方法，分两步：

1. 将列表所有元素原封不动地添加到堆中（数组即完全二叉树的层序存储，此时堆性质尚未满足）；
2. 倒序遍历（层序遍历的倒序），依次对每个非叶节点执行"从顶至底堆化"（sift_down）。

两个关键性质保证了该方法的正确性：

• 叶节点天然就是合法的子堆——它们没有子节点，无须堆化。因此遍历的起点是"最后一个节点的父节点"，即最后一个非叶节点；
• 每当堆化一个节点后，以该节点为根的子树就形成一个合法的子堆。由于采用倒序遍历，处理某个节点时，它之下的所有子树必然已经堆化完成，当前节点向下的堆化才是有效的。堆因此是**"自下而上"构建**的。

"从顶至底堆化"在 my_heap.py 中实现为 sift_down()：比较当前节点与左右子节点，找出三者中最大者 ma，若 ma != i 则交换并继续下探，直到当前节点已是局部最大或到达叶层：

def sift_down(self, i: int):
    """从节点 i 开始，从顶至底堆化"""
    while True:
        # 判断节点 i, l, r 中值最大的节点，记为 ma
        l, r, ma = self.left(i), self.right(i), i
        if l < self.size() and self.max_heap[l] > self.max_heap[ma]:
            ma = l
        if r < self.size() and self.max_heap[r] > self.max_heap[ma]:
            ma = r
        # 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
        if ma == i:
            break
        self.swap(i, ma)
        i = ma

各语言构造方法源码对照

文档中 [file]{my_heap}-[class]{max_heap}-[func]{__init__} 对应的构造方法，在仓库多种语言实现里高度一致，核心都是"原封不动拷贝 + 从最后一个非叶节点倒序 sift_down"：

Python —— my_heap.py：

def __init__(self, nums: list[int]):
    """构造方法，根据输入列表建堆"""
    # 将列表元素原封不动添加进堆
    self.max_heap = nums
    # 堆化除叶节点以外的其他所有节点
    for i in range(self.parent(self.size() - 1), -1, -1):
        self.sift_down(i)

Java —— my_heap.java：

public MaxHeap(List<Integer> nums) {
    maxHeap = new ArrayList<>(nums);
    // 堆化除叶节点以外的其他所有节点
    for (int i = parent(size() - 1); i >= 0; i--) {
        siftDown(i);
    }
}

C++ —— my_heap.cpp：

MaxHeap(vector<int> nums) {
    maxHeap = nums;
    // 堆化除叶节点以外的其他所有节点
    for (int i = parent(size() - 1); i >= 0; i--) {
        siftDown(i);
    }
}

Rust —— my_heap.rs 用 .rev() 优雅地表达了"倒序遍历"：

fn new(nums: Vec<i32>) -> Self {
    let mut heap = MaxHeap { max_heap: nums };
    // 堆化除叶节点以外的其他所有节点
    for i in (0..=Self::parent(heap.size() - 1)).rev() {
        heap.sift_down(i);
    }
    heap
}

这些实现共同依赖三个索引映射公式（见 my_heap.py），它们是数组表示完全二叉树的基础：

公式	含义
left(i) = 2i + 1	左子节点索引
right(i) = 2i + 2	右子节点索引
parent(i) = (i - 1) // 2（向下整除）	父节点索引

由此可以推断，遍历起点 parent(size() - 1) 正是"最后一个节点的父节点"——即最后一个非叶节点，与文档"我们从它开始倒序遍历并执行堆化"的表述完全吻合。

各语言文件的 Driver Code 都给出了可运行的验证入口，例如 my_heap.py 用列表 [9, 8, 6, 6, 7, 5, 2, 1, 4, 3, 6, 2] 建堆，随后依次演示 peek()、push(7)、pop()、size()、is_empty()，可直接运行观察建堆后的层序结构。

复杂度分析：从 $O(n \log n)$ 粗估到 $O(n)$ 严格推导

先给出朴素上界：

• 设完全二叉树节点数量为 $n$，则叶节点数量为 $(n + 1) / 2$（$/$ 为向下整除），需要堆化的节点数量为 $n / 2$；
• 从顶至底堆化时，每个节点最多下沉到叶节点，最大迭代次数为树高 $\log n$。

两者相乘得到 $O(n \log n)$。但这个估算不准确，因为它忽略了"底层节点数量远多于顶层节点"这一关键性质：需要下沉很深的节点（顶层少数节点）极少，而大量节点（底层）只需下沉一两次。

为精确计算，文档做了一个简化假设：给定节点数为 $n$、高度为 $h$ 的完美二叉树（每层节点数恰为 $2^0, 2^1, \dots, 2^h$），该假设不影响渐近结论。每个节点"从顶至底堆化"的最大迭代次数恰等于该节点到叶层的距离，即节点高度。因此对所有层"节点数量 × 节点高度"求和，得全部堆化迭代次数总和：

$$T(h) = 2^0 h + 2^1 (h - 1) + 2^2 (h - 2) + \dots + 2^{h-1} \times 1$$

化简借助错位相减法。将 $T(h)$ 乘以 2 后两式相减：

$$\begin{aligned} T(h) &= 2^0 h + 2^1 (h - 1) + \dots + 2^{h-1} \times 1 \\ 2T(h) &= 2^1 h + 2^2 (h - 1) + \dots + 2^h \times 1 \end{aligned}$$

$$2T(h) - T(h) = T(h) = -2^0 h + 2^1 + 2^2 + \dots + 2^{h-1} + 2^h$$

后一尾部分是首项为 2、公比为 2 的等比数列，直接套用求和公式 $\sum_{i=1}^{h} 2^i = 2^{h+1} - 2$，得到：

$$\begin{aligned} T(h) &= 2 \cdot \frac{1 - 2^h}{1 - 2} - h \\ &= 2^{h+1} - h - 2 \\ &= O(2^h) \end{aligned}$$

再代入完美二叉树的节点数 $n = 2^{h+1} - 1$，可得 $O(2^h) = O(n)$。

**结论：输入列表并建堆的时间复杂度为 $O(n)$，非常高效。**这也解释了为什么优先队列的批量初始化都选择"建堆 + 逐个出队"，而不是"逐个入队"。

建堆操作在仓库中的应用场景

从源码结构看，O(n) 建堆在《Hello 算法》仓库中至少有两类典型落地：

1. 堆排序的建堆阶段 —— heap_sort.py 的第一阶段就是原地建堆：

def heap_sort(nums: list[int]):
    """堆排序"""
    # 建堆操作：堆化除叶节点以外的其他所有节点
    for i in range(len(nums) // 2 - 1, -1, -1):
        sift_down(nums, len(nums), i)
    # 从堆中提取最大元素，循环 n-1 轮
    for i in range(len(nums) - 1, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        sift_down(nums, i, 0)

注意此处起点写为 len(nums) // 2 - 1，与 parent(size() - 1) 等价（当 $n$ 为偶数时最后节点的父节点是 $n/2 - 1$，当 $n$ 为奇数时 $n/2 - 1$ 处的节点无子节点、sift_down 直接空转，无副作用），这正是"最后一个非叶节点"这一原理的不同代数写法。建堆阶段为 $O(n)$，后续 $n - 1$ 轮"交换根节点 + 向下堆化"合计 $O(n \log n)$，堆排序总复杂度由后者主导。

2. 标准库优先队列的批量建堆 —— 各语言内置堆/优先队列的"由列表构造"接口内部即采用本文的方法二，例如 heap.md 中给出的 heapq.heapify(min_heap)、C++ priority_queue 以迭代器区间构造、Java new PriorityQueue<>(Arrays.asList(...))、Rust BinaryHeap::from(vec![...]) 等，均属 O(n) 建堆路径，与仓库中手写实现 MaxHeap(nums) 的构造逻辑一一对应。

此外，top_k.py 中"取最大 k 个元素"的解法虽以逐个 heappush 维护一个长度为 $k$ 的小顶堆为主，但它同样受益于"先放 k 个元素、再对剩余元素做条件替换"的批量思路——可见建堆思想是堆类应用的公共底座。

两种建堆方法对比

维度	方法一：逐个入堆	方法二：倒序遍历堆化
构建方向	自上而下（新节点从堆底上顶）	自下而上（非叶节点从顶下沉）
依赖的原语	push() + sift_up()	sift_down()
需要堆化的节点	全部 $n$ 个	仅约 $n/2$ 个非叶节点
时间复杂度	$O(n \log n)$	$O(n)$
空间复杂度	$O(1)$（原地/复用列表）	$O(1)$（原地）
适用场景	流式到达、动态维护的堆	一次性持有完整列表的批量初始化

小结

• 建堆有两种路线：复用 push() 逐个入堆得 $O(n \log n)$；"原封不动拷贝 + 从最后一个非叶节点倒序执行 sift_down"得 $O(n)$。
• 倒序遍历的正确性来自两个性质：叶节点天然合法、堆化某节点后其子树即成合法子堆；起点 parent(size() - 1) 即最后一个非叶节点。
• $O(n)$ 的严格证明依赖于完美二叉树分层求和 $T(h) = \sum 2^i(h - i)$，经错位相减化简为 $T(h) = 2^{h+1} - h - 2 = O(2^h) = O(n)$；$O(n \log n)$ 只是把"所有节点都下沉到底"的粗糙上界。
• 仓库中 my_heap.py、my_heap.java、my_heap.cpp、my_heap.rs 的构造方法，以及 heap_sort.py 的建堆阶段，均可作为可直接运行验证的实现参照。