Hello 算法：建堆（Heapify）操作详解——从 O(n log n) 到 O(n) 的两种构建路径-开发者社区

Hello 算法：建堆（Heapify）操作详解——从 O(n log n) 到 O(n) 的两种构建路径

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本篇技术指南以《Hello 算法》繁中版建堆積操作为核心骨架，讲解如何将一个普通列表（数组）原地构建为合法的堆结构：既介绍朴素直观的"逐个入堆"法，也重点推导高效实用的"倒序堆化"法，并给出其在 Python、Java、C++、C、Go、JavaScript、TypeScript 等多语言实现中的源码级证据。读完本文，你将掌握两种建堆方法的时间复杂度差异、O(n) 建堆的数学原理，以及如何在项目中直接复用仓库中MaxHeap的构造逻辑。

一、什么是建堆操作

在某些场景下，我们希望直接用列表（数组）的全部元素构建一个堆，而不是从空堆开始逐个插入元素。这个"用已有数据一次性构建堆"的过程，在《Hello 算法》中被称为建堆操作（heapify / build-heap）。

以仓库中的 Python 实现为例，my_heap.py 中的MaxHeap类既支持空堆初始化，也支持传入列表直接建堆——这正是本章讨论的核心场景。围绕这一操作，存在两条实现路径：

构建方法	构建方向	时间复杂度	核心操作
借助入堆操作	自上而下	O(n log n)	逐个`push`+ 从底至顶堆化（`siftUp`）
倒序遍历堆化	自下而上	O(n)	原地放置 + 从顶至底堆化（`siftDown`）

下面分别展开。

二、方法一：借助入堆操作，自上而下构建（O(n log n)）

这是最直观的思路：先建立一个空堆，然后遍历列表，依次对每个元素执行"入堆操作"。

入堆操作的完整流程是：先将元素添加到堆的尾部，再对该元素执行从底至顶堆化（siftUp），让它在不断与父节点比较、交换的过程中上升到合适位置。仓库中 Python 实现如下：

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: # 获取节点 i 的父节点 p = self.parent(i) # 当“越过根节点”或“节点无须修复”时，结束堆化 if p < 0 or self.max_heap[i] <= self.max_heap[p]: break # 交换两节点 self.swap(i, p) # 循环向上堆化 i = p

可以看出，每处理一个元素，堆的长度就加一；由于节点是从顶到底依次被添加进完全二叉树的，因此这种建堆方式是**"自上而下"**的。对于 n 个元素，每个元素的入堆操作需要 O(log n) 时间（最坏需从叶节点一路交换到根），因此该建堆方法的整体时间复杂度为：

$$O(n \log n)$$

结论虽然正确，但效率并非最优——我们完全可以做得更好。

三、方法二：倒序遍历堆化，自下而上构建（O(n)）

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

原封不动地放置：将列表所有元素直接放入堆的数组表示中，此时堆的性质尚未满足；
倒序遍历堆化：倒序遍历堆（即层序遍历的倒序），依次对每个非叶节点执行"从顶至底堆化"（siftDown）。

3.1 为什么必须倒序遍历

关键原因在于：每当堆化一个节点后，以该节点为根节点的子树就形成一个合法的子堆。由于是倒序遍历，当处理到某个节点时，它之下的子树必然已经是合法的子堆，此时再对该节点执行堆化才是有效的——就像自下而上逐层"浇筑"地基。

反过来，如果采用正序遍历，处理上层节点时其下层子树尚未合法，堆化结果会被后续操作破坏，无法一次性保证全局堆性质。

3.2 叶节点无需堆化

叶节点没有子节点，天然就是合法的子堆，无须执行堆化。因此遍历的起点不是数组末尾，而是最后一个非叶节点——即最后一个节点的父节点。以仓库 Python 实现为例：

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)

其中parent与siftDown的对应实现（my_heap.py）：

def parent(self, i: int) -> int: """获取父节点的索引""" return (i - 1) // 2 # 向下整除 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

3.3 多语言实现的一致性

该构造逻辑在仓库全部语言实现中保持高度一致，均遵循"从parent(size()-1)递减到 0 逐个siftDown"的模式，可交叉对照学习：

Java：my_heap.java 使用List<Integer>存储，for (int i = parent(size() - 1); i >= 0; i--) siftDown(i)；
C++：my_heap.cpp 使用vector<int>，构造时将入参列表直接拷贝给成员后倒序堆化；
C：my_heap.c 使用预分配数组data[MAX_SIZE]，newMaxHeap中通过memcpy一次性拷贝全部元素；
Go：my_heap.go 使用切片，newMaxHeap直接复用传入切片h := &maxHeap{data: nums}后倒序堆化；
JavaScript：my_heap.js 与TypeScript：my_heap.ts 通过展开运算符[...nums]拷贝列表后执行相同流程。

从源码结构可以推断，该建堆过程是在列表自身（或其拷贝）上原地完成堆化的，不需要额外的 O(n) 辅助数组，这也是它常被用于大规模数据初始化的原因之一。

四、复杂度分析：为什么是 O(n) 而不是 O(n log n)

4.1 粗略估算为何不准确

先做一个朴素估算：

假设完全二叉树的节点数量为 n，则叶节点数量为 (n + 1) / 2（其中 / 为向下整除），因此需要堆化的节点数量约为 n / 2；
在从顶至底堆化的过程中，每个节点最多堆化到叶节点，最大迭代次数为二叉树高度 log n。

将两者相乘，得到建堆时间复杂度约为 O(n log n)。但这个估算并不准确，因为它没有考虑二叉树底层节点数量远多于顶层节点这一性质——底层节点虽然多，但各自只需堆化很少几步，粗算把每个节点都按满高度 log n 计算，严重高估了总工作量。

4.2 精确推导：逐层求和

为了精确计算，我们假设给定一个节点数量为 n、高度为 h 的完美二叉树（该假设不影响计算结果的正确性）。下图展示了完美二叉树各层的节点数量：

节点"从顶至底堆化"的最大迭代次数，等于该节点到叶节点的距离，也就是节点高度。因此，对每一层计算"节点数量 × 节点高度"，再对所有层求和，即可得到全部节点堆化迭代次数的总和 T(h)：

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

4.3 错位相减法化简

化简上式需要借助数列知识。先将 T(h) 乘以 2，得到：

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

使用错位相减法，用下式 2T(h) 减去上式 T(h)，可得：

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

观察上式，T(h) 的主体是一个等比数列，可直接使用求和公式：

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

进一步地，高度为 h 的完美二叉树节点数量为 n = 2^{h+1} - 1，因此易得：

$$O(2^h) = O(n)$$

以上推算表明：输入列表并建堆的时间复杂度为 O(n)，非常高效。这也解释了为什么在实际工程中，用heapify批量初始化堆（例如 Top-K 问题的建堆阶段）远优于逐个push插入。

五、源码级验证：驱动代码与运行入口

仓库中每种语言都为MaxHeap配备了可直接运行的驱动代码，便于实证建堆行为。以 Python 驱动代码为例，其测试列表为[9, 8, 6, 6, 7, 5, 2, 1, 4, 3, 6, 2]：

"""Driver Code""" if __name__ == "__main__": # 初始化大顶堆 max_heap = MaxHeap([9, 8, 6, 6, 7, 5, 2, 1, 4, 3, 6, 2]) print("\n输入列表并建堆后") max_heap.print() # 获取堆顶元素 peek = max_heap.peek() print(f"\n堆顶元素为 {peek}") # ...（入堆、出堆、大小、判空等验证）

运行后，print()会借助modules中的print_heap工具将数组渲染为树形结构打印。相同测试用例在 Java、C++、Go、JavaScript 等实现中均可见，可对照验证：无论采用何种语言，MaxHeap([9, 8, 6, 6, 7, 5, 2, 1, 4, 3, 6, 2])建堆后堆顶元素（最大值）均为 9，且整棵树满足大顶堆性质——即每个父节点的值不小于其子节点。