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.pydef 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 ma3.3 多语言实现的一致性该构造逻辑在仓库全部语言实现中保持高度一致均遵循从parent(size()-1)递减到 0 逐个siftDown的模式可交叉对照学习Javamy_heap.java 使用ListInteger存储for (int i parent(size() - 1); i 0; i--) siftDown(i)Cmy_heap.cpp 使用vectorint构造时将入参列表直接拷贝给成员后倒序堆化Cmy_heap.c 使用预分配数组data[MAX_SIZE]newMaxHeap中通过memcpy一次性拷贝全部元素Gomy_heap.go 使用切片newMaxHeap直接复用传入切片h : maxHeap{data: nums}后倒序堆化JavaScriptmy_heap.js 与TypeScriptmy_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^{h1} - h - 2 \newline O(2^h) \end{aligned}$$进一步地高度为 h 的完美二叉树节点数量为 n 2^{h1} - 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且整棵树满足大顶堆性质——即每个父节点的值不小于其子节点。六、小结与延伸阅读建堆操作是用列表元素一次性构建堆的过程有逐个入堆O(n log n)自上而下与倒序堆化O(n)自下而上两种实现O(n) 建堆的关键在于非叶节点数量约 n/2且越靠近底层、节点越多但堆化步数越少二者加权后的总工作量呈线性增长工程选型建议若数据已整体就绪应优先使用倒序堆化批量建堆若数据是动态流入、需要随时保持堆结构则应使用逐个入堆。进一步阅读同章节内容可深入理解堆的基础结构与操作细节堆積堆的数组表示与基本操作、建堆積操作本文主题原文、Top-K 問題堆在实际问题中的典型应用以及章节总结 小結。【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考