《Hello 算法》堆章节精读：完全二叉树的优先队列实现、O(n) 建堆与 Top-k 问题全解析

《Hello 算法》堆章节精读：完全二叉树的优先队列实现、O(n) 建堆与 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

本篇技术指南以仓库中堆章节的总结文档 ru/docs/chapter_heap/summary.md 为骨架，系统梳理"堆（heap）"这一数据结构的完整知识闭环：从大顶堆 / 小顶堆的定义、优先队列接口、数组存储与索引映射，到入堆出堆的核心堆化过程、可优化至 O(n) 的建堆技巧，再到经典 Top-k 问题的三种解法对比。读完本文，你将能徒手实现一个堆、用源码级细节解释为何建堆是 O(n) 而非 O(n log n)，并能把堆直接应用到"求前 k 大元素"的真实场景中。

一、核心结论速览：这一章你到底该记住什么

按照 ru/docs/chapter_heap/summary.md 中的"重点回顾"，本章的全部技术要点可以浓缩为以下 7 条：

• 堆是一棵完全二叉树，按成立条件分为大顶堆（max heap）与小顶堆（min heap）；大（小）顶堆的堆顶元素即全局最大（小）值。
• 优先队列的定义是"带有出队优先级的队列"，工程上通常用堆来实现。
• 堆的常用操作时间复杂度：元素入堆 O(log n)、堆顶元素出堆 O(log n)、访问堆顶元素 O(1)。
• 完全二叉树非常适合用数组表示，因此堆通常以数组存储。
• **堆化（heapify）**用于维护堆的性质，在入堆、出堆操作中都会用到。
• 输入 n 个元素一次性建堆的时间复杂度可以优化至O(n)，非常高效。
• Top-k是经典算法问题，用堆可在O(n log k)时间内高效求解。

这 7 条结论分别对应本章正文的 4 篇文档（俄语版位于 ru/docs/chapter_heap/ 目录，中文原版位于 docs/chapter_heap/ 目录）。下面逐条展开讲解，并结合仓库源码验证其正确性。

二、堆的本质：满足特定条件的完全二叉树

堆（heap）是满足特定条件的完全二叉树，分为两类：

• 小顶堆（min heap）：任意节点的值 ≤ 其子节点的值；
• 大顶堆（max heap）：任意节点的值 ≥ 其子节点的值。

作为完全二叉树的特例，堆还具备以下结构特性（见 ru/docs/chapter_heap/heap.md）：

• 最底层节点靠左排列，其余各层全部填满；
• 二叉树的根节点称为堆顶（top of heap），最底层最右侧的节点称为堆底（bottom of heap）；
• 在大（小）顶堆中，堆顶元素即根节点的值始终是最大（小）值。

关键推论：因为只保证"父子之间"的偏序关系、不保证"兄弟之间"的序关系，堆并不是完全有序的结构——它只保证堆顶的极值，这一点正是它能在 O(log n) 内完成插入与删除的根基。若要对全部数据排序，则需配合"堆排序"，见下文典型应用一节。

三、优先队列：语言内置的堆接口与操作复杂度

需要特别说明的是，很多编程语言并不直接暴露"堆"这个类型，而是提供优先队列（priority queue）——一种"按优先级出队"的抽象数据结构。实践中最常见的做法是用堆实现优先队列，其中大顶堆等价于"按降序出队的优先队列"。因此在 ru/docs/chapter_heap/heap.md 中作者明确约定：不再刻意区分二者，统一以"堆"称呼。

堆的常用操作及其时间复杂度如下表：

具体的方法命名随语言而异。例如在 codes/python/chapter_heap/heap.py 中，Python 的heapq模块默认只提供小顶堆；若想构造大顶堆，可以在入堆前对元素取负，从而颠倒大小关系。正文中用flag = 1 / -1来统一表达这种切换：

import heapq # 初始化小顶堆 min_heap, flag = [], 1 # 初始化大顶堆：入堆前先乘 -1，把大小关系颠倒 max_heap, flag = [], -1 # 元素入堆 heapq.heappush(max_heap, flag * 1) heapq.heappush(max_heap, flag * 3) heapq.heappush(max_heap, flag * 2) heapq.heappush(max_heap, flag * 5) heapq.heappush(max_heap, flag * 4) # 访问堆顶（大顶堆的最大值） peek: int = flag * max_heap[0] # 5 # 堆顶元素出堆：依次得到 5、4、3、2、1 val = flag * heapq.heappop(max_heap) # 5 val = flag * heapq.heappop(max_heap) # 4 # 由输入列表直接建堆 min_heap = [1, 3, 2, 5, 4] heapq.heapify(min_heap)

类似的写法在 C++（priority_queue+greater/less）、Java/Kotlin（PriorityQueue+ 自定义Comparator）、Rust（BinaryHeap+Reverse）等语言的 codes/ 各子目录chapter_heap/中均有完整实现，可以直接对照查阅。

四、数组存储与索引映射：用下标代替指针

完全二叉树的一大优势是无需指针即可用数组存储：元素值按层序填入数组，节点间关系完全由索引公式推导（见 ru/docs/chapter_heap/heap.md）。

对索引为 i 的节点，其三个关键位置的索引为：

• 左子节点：2i + 1
• 右子节点：2i + 2
• 父节点：(i - 1) / 2（向下取整）

索引越界即代表空节点。这些公式被封装为left、right、parent三个方法，见 codes/python/chapter_heap/my_heap.py：

def left(self, i: int) -> int: """获取左子节点的索引""" return 2 * i + 1 def right(self, i: int) -> int: """获取右子节点的索引""" return 2 * i + 2 def parent(self, i: int) -> int: """获取父节点的索引""" return (i - 1) // 2 # 向下整除

正是基于这套映射，peek()（访问堆顶）在 my_heap.py 中退化为一条语句return self.max_heap[0]，时间复杂度为 O(1)。在 C 语言实现 codes/c/chapter_heap/my_heap.c 中，同样的公式直接作用于定长数组data[MAX_SIZE]（MAX_SIZE定义为 5000，见第 9 行），且父节点索引通过整数除法(i - 1) / 2天然实现向下取整。

五、入堆与出堆：两个方向的堆化过程

**堆化（heapify）**是堆的"自愈"机制：一旦插入或删除破坏了堆的性质，就沿着一条路径反复比较、交换，直到整棵树重新满足条件。

5.1 元素入堆：从底至顶堆化（sift up）

入堆分三步（ru/docs/chapter_heap/heap.md）：

1. 将新元素val追加到堆底（数组末尾）；
2. 从该节点出发，与其父节点比较：若新节点更大，则交换二者；
3. 沿路径继续向上比较，直到越过根节点或遇到无需交换的节点为止。

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

以上代码见 codes/python/chapter_heap/my_heap.py。C 语言版本 codes/c/chapter_heap/my_heap.c 在入堆前还会做容量检查（size == MAX_SIZE时报 "heap is full!"）。

5.2 堆顶出堆：从顶至底堆化（sift down）

出堆若直接删除数组首元素，会导致所有节点索引整体偏移，令后续堆化难以进行。因此采用"先换后删"的经典策略（见 ru/docs/chapter_heap/heap.md 与 my_heap.py）：

1. 交换堆顶元素与堆底元素（即根节点与最右叶节点）；
2. 删除现在的堆底——由于上一步已交换，实际删除的是原堆顶；
3. 从新的根节点开始，执行从顶至底的堆化：比较当前节点与其左右子节点，与值最大的子节点交换，不断向下，直到到达叶节点或无需交换。

def pop(self) -> int: """元素出堆""" if self.is_empty(): raise IndexError("堆为空") # 交换根节点与最右叶节点（交换首元素与尾元素） self.swap(0, self.size() - 1) # 删除节点 val = self.max_heap.pop() # 从顶至底堆化 self.sift_down(0) # 返回堆顶元素 return val 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

由于完全二叉树的高度为 O(log n)，堆化路径上最多迭代 O(log n) 次，因此入堆与出堆的时间复杂度均为 O(log n)，与正文结论表完全一致。C 语言的pop还会在堆为空时打印 "heap is empty!" 并返回INT_MAX作为哨兵，见 codes/c/chapter_heap/my_heap.c。

六、O(n) 建堆：为什么比"逐个插入"更快

当需要一次性用全部 n 个元素建堆时，有两种思路（见 ru/docs/chapter_heap/build_heap.md）。

6.1 方法一：反复入堆，复杂度 O(n log n)

创建空堆后遍历列表，对每个元素执行一次入堆。由于每次入堆 O(log n)，总复杂度为 O(n log n)，且逐层"自上而下"建堆。

6.2 方法二：整体放入后自底向上堆化，复杂度 O(n)

更高效的做法只有两步：

1. 将列表元素原封不动放入堆（此刻并不满足堆的性质）；
2. 逆序按层遍历（跳过所有叶节点），对每个非叶节点执行一次从顶至底的sift_down。

之所以必须逆序遍历，是因为它能保证：处理当前节点时，其下方子树已经是合法的子堆，此时对当前节点做下沉堆化才真正有效。叶节点天然是合法子堆（没有子节点需要比较），无需处理；第一个需要处理的非叶节点就是"最后一个节点的父节点"。

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)

见 codes/python/chapter_heap/my_heap.py；C 语言同款newMaxHeap构造逻辑位于 codes/c/chapter_heap/my_heap.c。

6.3 复杂度分析的精髓：把"每层节点数"算进去

粗看每个节点下沉至多 O(log n)，n/2 个非叶节点相乘似乎是 O(n log n)。但这个上界过松：完全二叉树中越靠下的层节点越多，而越靠下的节点距叶子的高度越小。

对高度为 h 的理想二叉树做精确求和：某节点下沉的最大迭代次数等于它的"高度"（到叶子的距离），于是对所有层求和：

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

采用错位相减法（将 T(h) 乘以 2 再与原式相减）可得：

$$ T(h) = 2^{h+1} - h - 2 = O(2^h) $$

而高度 h 的理想二叉树节点数 n = 2^(h+1) − 1，故O(2^h) = O(n)。这意味着：将输入列表整体建堆的时间复杂度是O(n) 而非 O(n log n)。

直觉层面的解释是：堆化总工作量约等于"全部节点的高度之和"，这个和恰好收敛为 O(n)。这也是 ru/docs/chapter_heap/build_heap.md 给出的完整推导（heap.py 的驱动代码也注释道："输入列表并建堆的时间复杂度为 O(n)，而非 O(nlogn)"）。

七、经典实战：Top-k 问题的三种解法

Top-k 是堆的招牌应用，问题定义为：给定长度为 n 的无序数组nums，返回其中最大的 k 个元素（见 ru/docs/chapter_heap/top_k.md）。

7.1 方法一：k 轮遍历，O(nk)

对数组做 k 轮扫描，每轮挑出当前最大元素。当 k 很小时勉强可用，但当 k → n 时复杂度退化至 O(n²)。若 k = n，此问题退化为"选择排序"，得到全序排列。

7.2 方法二：整体排序，O(n log n)

先对数组做全量排序再取最右侧 k 个元素。显然"杀鸡用牛刀"——我们只关心前 k 个最大元素，没必要为剩余 n − k 个元素付出排序代价。

7.3 方法三：维护大小为 k 的小顶堆，O(n log k)

堆解法的精妙之处在于用小顶堆存"当前最大的 k 个"，堆顶恰好是这 k 个里的最小值（门槛值）：

1. 初始化一个小顶堆；
2. 先将数组前 k 个元素入堆；
3. 从第 k+1 个元素起遍历：若当前元素大于堆顶（门槛值），则弹出堆顶、将当前元素入堆；
4. 遍历结束后，堆中恰好保存最大的 k 个元素。

仓库中的完整实现位于 codes/python/chapter_heap/top_k.py：

def top_k_heap(nums: list[int], k: int) -> list[int]: """基于堆查找数组中最大的 k 个元素""" # 初始化小顶堆 heap = [] # 将数组的前 k 个元素入堆 for i in range(k): heapq.heappush(heap, nums[i]) # 从第 k+1 个元素开始，保持堆的长度为 k for i in range(k, len(nums)): # 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆 if nums[i] > heap[0]: heapq.heappop(heap) heapq.heappush(heap, nums[i]) return heap

全程共执行 n 次入堆 / 出堆，堆的最大长度为 k，因此复杂度为O(n log k)：k 小时趋近 O(n)，k 大时也不超过 O(n log n)。该方法还天然适配动态数据流：数据持续到达时只需不断维护这个固定大小的小顶堆，即可随时查询当前最大的 k 个元素，无需重算。

说明：驱动代码以nums = [1, 7, 6, 3, 2], k = 3为例，运行后打印堆化的树形结构，详见 top_k.py。

八、堆的典型应用回顾

依据正文 ru/docs/chapter_heap/heap.md 的总结，堆的主要应用场景包括：

• 优先队列：堆几乎是实现优先队列的首选结构——入堆出堆 O(log n)、建堆 O(n)，各操作均十分高效；
• 堆排序：给定数据集时，可先建堆再不断弹出堆顶，从而获得有序序列；工程上还有更精巧的就地堆排序写法，见排序章节 docs/chapter_sorting/heap_sort.md；
• 求最大 k 个元素（Top-k）：如前文所述，典型如排行榜中挑选热度最高的 10 条新闻、销量最高的 10 件商品等场景。

九、答疑解惑：数据结构的"堆"与内存管理的"堆"是同一个概念吗？

这是堆章节最容易被混淆的概念，ru/docs/chapter_heap/summary.md 的 Q&A 给出了明确回答：

两者不是同一个概念，只是碰巧都叫"堆"（heap）。计算机系统内存中的"堆"是动态内存分配的一部分：程序运行时可以在堆区申请内存，用来存放对象、数组等复杂结构；当这些数据不再需要时，程序必须显式释放内存以防内存泄漏。相较栈内存，堆内存的分配与释放需要更谨慎地管理，使用不当容易引发内存泄漏、野指针（悬空指针）等问题。

数据结构的"堆"则纯粹是一种逻辑上的树形组织方式，与内存物理布局没有任何关系。仓库中关于"栈与堆"的内存差异还可参阅 docs/chapter_array_and_linkedlist/ram_and_cache.md 等章节中对内存模型的讲解。

十、如何在仓库中验证本章全部结论

堆章节的全部代码示例以统一命名组织在各语言目录下，可直接查阅、运行：

例如在仓库根目录执行：

python3 codes/python/chapter_heap/my_heap.py # 手写大顶堆：建堆、入堆、出堆全流程 python3 codes/python/chapter_heap/heap.py # heapq 小顶堆与大顶堆取负技巧 python3 codes/python/chapter_heap/top_k.py # Top-k：打印最大的 3 个元素

即可亲眼验证：入堆后堆顶为最大值、连续出堆得到降序序列、heapq.heapify一次性建堆等行为。若想进一步理解手写实现的单元测试式驱动代码，可对照 codes/c/chapter_heap/my_heap_test.c（C 语言测试文件）与 codes/python/chapter_heap/my_heap.py 底部 Driver Code。至此，堆从"定义 → 存储 → 操作 → 建堆 → 应用 → 概念辨析"的完整知识链即可全部打通。

【免费下载链接】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