《Hello 算法》堆（Heap）完全指南：大顶堆与小顶堆原理、常用操作与数组实现

堆是一种以完全二叉树为基础的高效数据结构，在优先队列、Top-K、堆排序等经典算法场景中扮演核心角色。本文以仓库俄文版文档 heap.md 为骨架（其内容与 中文版 完全一致），系统讲解堆的定义与性质、push / pop / peek / size / isEmpty 等常用操作，并深入到堆的数组存储、自底向上堆化与自顶向下堆化的完整实现原理，最后结合 my_heap.py、my_heap.c、top_k.py 等仓库源码给出可运行、可验证的实战参考。

什么是堆：满足特定条件的完全二叉树

堆（heap）是一种满足特定条件的完全二叉树，主要可分为两种类型：

• 小顶堆（min heap）：任意节点的值 $\leq$ 其子节点的值，因此堆顶（根节点）是全局最小值；
• 大顶堆（max heap）：任意节点的值 $\geq$ 其子节点的值，因此堆顶是全局最大值。

作为完全二叉树的一个特例，堆具有以下三个结构性特征：

• 最底层节点靠左填充，其余各层节点均被填满（这正是“完全”二字的含义）；
• 将二叉树的根节点称为堆顶，将最底层最靠右的节点称为堆底；
• 对于大顶堆（小顶堆），堆顶元素（根节点）的值是最大（最小）的。

需要特别说明的是，堆只约束“父节点与子节点之间”的偏序关系，并不要求同一层兄弟节点之间存在任何有序性，这与二叉搜索树要求左子树小于根、右子树大于根的全局有序约束有本质区别。因此堆只能保证快速取得极值，而不能像二叉搜索树那样做中序遍历得到有序序列。

堆的常用操作：方法与复杂度一览

在实际使用中，许多编程语言直接提供的是 优先队列（priority queue）——一种按优先级出队的抽象数据结构。事实上，堆通常被用来实现优先队列，大顶堆等价于元素按从大到小顺序出队的优先队列。从使用角度看，可以将“优先队列”与“堆”视为等价的数据结构。因此本书对二者不做特别区分，统一称为“堆”。

堆的核心操作及其时间复杂度如下表所示（具体方法名因语言而异）：

方法名	描述	时间复杂度
push()	元素入堆	$O(\log n)$
pop()	堆顶元素出堆	$O(\log n)$
peek()	访问堆顶元素（大 / 小顶堆分别为最大 / 最小值）	$O(1)$
size()	获取堆的元素数量	$O(1)$
isEmpty()	判断堆是否为空	$O(1)$

入堆与出堆之所以是 $O(\log n)$，是因为每次操作最多沿树高（即 $O(\log n)$）调整一次堆序；而读取堆顶、获取大小、判空只触及堆顶元素或长度字段，因此均为 $O(1)$。

大顶堆与小顶堆的切换：flag 与 Comparator

类似排序中的“从小到大”与“从大到小”，可以通过设置一个 flag 或修改 Comparator 在“小顶堆”与“大顶堆”之间自由切换。

以仓库 codes/python/chapter_heap/heap.py 为例，Python 的 heapq 模块默认只实现小顶堆，通过“入堆前对元素取负”可以把大小关系颠倒，从而用同一份代码模拟出大顶堆：

import heapq

# 初始化小顶堆
min_heap, flag = [], 1
# 初始化大顶堆
max_heap, flag = [], -1
# flag = 1 对应小顶堆，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

# 堆顶元素出堆，出堆序列为从大到小
val = flag * heapq.heappop(max_heap)  # 5
val = flag * heapq.heappop(max_heap)  # 4
val = flag * heapq.heappop(max_heap)  # 3
val = flag * heapq.heappop(max_heap)  # 2
val = flag * heapq.heappop(max_heap)  # 1

# 获取堆大小
size: int = len(max_heap)

# 判断堆是否为空
is_empty: bool = not max_heap

# 输入列表并建堆：heapify 的时间复杂度为 O(n)
min_heap: list[int] = [1, 3, 2, 5, 4]
heapq.heapify(min_heap)

直接在 codes/python 目录下执行 python chapter_heap/heap.py，即可看到每次入堆 / 出堆后以二叉树形态打印的中间过程（打印借助 modules.print_heap 完成）。

各语言中的堆 API 对照

由于不同语言对堆的命名差异较大，下表汇总了对应类 / 模块与大小顶堆的构造方式，方便读者按语言直接查阅：

语言	使用对象	大小顶堆切换方式	入堆 / 出堆 / 取顶	说明
Python	heapq 模块	入堆前对元素取负	heappush / heappop / heap[0]	默认为小顶堆
C++	std::priority_queue	模板参数 greater<T> / less<T>	push / pop / top	默认大顶堆
Java	PriorityQueue	lambda Comparator	offer / poll / peek	默认小顶堆
C#	PriorityQueue<T, TP>	Comparer lambda	Enqueue / Dequeue / Peek	默认小顶堆
Go	container/heap	自定义 Less 中比较符号方向	heap.Push / heap.Pop / 自定义 Top	需实现 heap.Interface 与 sort.Interface
Swift	Heap<T>（swift-collections）	类本身同时支持两种堆	insert / removeMax / max()	需引入 swift-collections 库
Rust	BinaryHeap	Reverse<T> 包装	push / pop / peek	默认大顶堆
Kotlin	PriorityQueue	lambda Comparator	offer / poll / peek	默认小顶堆
JS / TS / Dart / C / Ruby	无内建堆类	—	—	需使用自定义实现或第三方库

以 Java 为例，默认 PriorityQueue 是小顶堆，传入 lambda 表达式 (a, b) -> b - a 后即为大顶堆：

Queue<Integer> minHeap = new PriorityQueue<>();
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

maxHeap.offer(1);
maxHeap.offer(3);
maxHeap.offer(2);
maxHeap.offer(5);
maxHeap.offer(4);

int peek = maxHeap.peek();          // 5
peek = maxHeap.poll();              // 5，出堆序列从大到小
boolean isEmpty = maxHeap.isEmpty();

C++ 中通过 std::priority_queue 的第三个模板参数控制方向：greater<int> 为小顶堆、默认的 less<int> 为大顶堆；还可直接用迭代器区间从既有容器建堆：priority_queue<int, vector<int>, greater<int>> minHeap(input.begin(), input.end())。

Go 语言没有内建的堆类，标准库 container/heap 要求自行实现接口：定义 type intHeap []any，同时实现 sort.Interface 的 Len / Less / Swap 与 heap.Interface 的 Push / Pop。其中 Less 使用 > 即为大顶堆、使用 < 即为小顶堆；Push 与 Pop 必须使用指针接收者，因为它们不仅修改切片内容还修改其长度。随后通过 heap.Init、heap.Push、heap.Pop 等标准库函数驱动堆行为，测试代码（TestHeap）展示了初始化、连续出堆得到递减序列、输出大小与判空结果的完整流程。

Rust 的 std::collections::BinaryHeap 默认是大顶堆，将元素包一层 Reverse<T> 即可得到小顶堆：BinaryHeap<Reverse<i32>>；最小堆也可通过 BinaryHeap::from(vec![Reverse(1), Reverse(3), ...]) 直接从既有数据构造。

堆的数组存储与索引映射

由于堆是完全二叉树，因此可以使用数组来存储堆：数组元素对应节点值，数组下标对应节点位置，父子关系通过下标公式推算，从而省去显式的左右孩子指针。

设节点下标为 $i$，则：

• 左子节点下标：$2i + 1$；
• 右子节点下标：$2i + 2$；
• 父节点下标：$\lfloor (i - 1) / 2 \rfloor$（向下取整）。

若计算出的下标越界，则表示对应节点为空或不存在。上述映射在 codes/python/chapter_heap/my_heap.py 中被封装为 left / right / parent 三个方法，它们也是后续所有堆操作共同依赖的基础设施：

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  # 向下整除

下面以大顶堆为例，逐一讲解堆顶访问、入堆与出堆的完整实现逻辑。若想将其改造为小顶堆，只需把全部大小比较反向（例如将 $\geq$ 换成 $\leq$），感兴趣的读者可以自行实现验证。

访问堆顶元素 peek

堆顶即二叉树的根节点，也就是数组的首个元素，直接返回 max_heap[0] 即可，时间复杂度为 $O(1)$。

元素入堆 push 与自底向上堆化 sift_up

入堆分为两步：先把元素 val 追加到堆底（即数组末尾），再修复堆序。由于新元素可能大于堆中部分节点，需要沿“被插入节点 → 根节点”的路径恢复堆序，这一修复过程称为堆化（heapify）。

自底向上堆化从刚插入的节点开始：比较该节点与父节点，若插入节点更大则交换二者；随后对父节点重复相同操作，一路向上，直到越过根节点，或遇到无须交换的节点为止。

仓库 codes/python/chapter_heap/my_heap.py 中的实现如下：

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)                      # 获取节点 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(\log n)$，入堆的时间复杂度为 $O(\log n)$。入堆的完整分步过程可参考文档配套的 heap_push_step1.png 至 heap_push_step9.png（见 heap.assets）：每一步对应一次比较与交换，直至新元素“上浮”到正确位置。

堆顶元素出堆 pop 与自顶向下堆化 sift_down

堆顶元素就是根节点，即数组的首个元素。但不能直接删除第一个元素——那样会导致所有节点下标整体左移，使后续按下标公式恢复堆序变得极为麻烦。为了尽量减少元素下标变动，标准做法分为三步：

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:
        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
        if ma == i:                             # 节点 i 已最大或子节点越界
            break
        self.swap(i, ma)                        # 交换两节点
        i = ma                                  # 循环向下堆化

与入堆一样，出堆也需要沿高度为 $O(\log n)$ 的路径修复，因此出堆的时间复杂度同样为 $O(\log n)$。分步过程可参见 heap_pop_step1.png 至 heap_pop_step10.png（位于 heap.assets），其中根节点一路与较大的子节点交换并“下沉”到最终位置。

从输入列表建堆

若需基于既有数组初始化堆，常见做法有两种：

• 调用语言自带接口线性建堆，如 Python 的 heapq.heapify，其时间复杂度为 $O(n)$ 而非 $O(n\log n)$；
• 使用自定义堆类的构造函数。在 my_heap.py 中，构造方法先将列表原样拷入 self.max_heap，随后从最后一个非叶节点（即最后一个元素的父节点）开始倒序对所有非叶节点执行 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)

C 语言版实现见 codes/c/chapter_heap/my_heap.c：其 newMaxHeap 用 memcpy 将输入数组拷入结构体内预分配的定长数组 data[MAX_SIZE]（MAX_SIZE 为 5000，预先分配避免扩容），再从 parent(size - 1) 起倒序调用 siftDown 完成建堆；push / pop / siftUp / siftDown 的算法流程与 Python 版一一对应，其中 push 在堆满（size == MAX_SIZE）与 pop 在堆空时均做了显式保护。该文件配套的测试入口 codes/c/chapter_heap/my_heap_test.c 通过打印建堆、入堆、出堆后的二叉树形态来验证每一步的正确性。

堆的自定义实现小结

至此，一个自研大顶堆的全部成员就齐备了。下表汇总了各操作与支撑方法的对应关系：

操作	时间复杂度	依赖的辅助方法
peek() 取堆顶	$O(1)$	max_heap[0]
push(val) 入堆	$O(\log n)$	append + sift_up
pop() 出堆	$O(\log n)$	首尾交换 + sift_down
size() / is_empty()	$O(1)$	len
构造建堆	$O(n)$	从最后一个非叶节点倒序 sift_down

堆的典型应用

综合全文，堆在工程与算法中最常见的三类应用如下：

• 优先队列：堆是优先队列的首选底层实现。入堆与出堆均为 $O(\log n)$、建堆为 $O(n)$，整体效率极高，是任务调度、Dijkstra 最短路、哈夫曼编码等众多经典算法的基石；
• 堆排序：对给定数据先建堆，再不断取出堆顶元素即可得到有序序列。工程上通常采用更精巧的就地堆排实现，可参考 堆排序 章节；
• 求最大（小）的 k 个元素（Top-K）：这是堆的经典考题与典型应用场景，例如选出 10 条最热门新闻、10 件最畅销商品等。

仓库中的 codes/python/chapter_heap/top_k.py 给出了基于小顶堆的 Top-K 参考实现：先用数组前 $k$ 个元素建小顶堆，随后扫描剩余元素——若当前元素大于堆顶（当前 k 个元素中的最小值），则弹出堆顶并入堆当前元素，始终保持堆大小为 $k$，遍历结束后堆中即为最大的 $k$ 个元素：

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

C 语言版 codes/c/chapter_heap/top_k.c 展示了另一种通用思路：由于 C 没有内建小顶堆，代码通过“入堆前取负、出堆 / 取顶后取负”的方式，用自定义 MaxHeap 模拟小顶堆——pushMinHeap 内部执行 push(maxHeap, -val)，popMinHeap 返回 -pop(maxHeap)，peekMinHeap 返回 -peek(maxHeap)，getMinHeap 则一次性将堆中元素取反拷出。这一手法与 Python 用 flag = -1 模拟大顶堆在思想上是同一枚硬币的两面。

小结与延伸阅读

本文围绕“堆”这一主题，从定义、性质、常用操作出发，借助 my_heap.py 与 my_heap.c 两个仓库实现，完整走通了数组存储、parent / left / right 索引映射、peek、push + sift_up、pop + sift_down 以及基于输入列表建堆的全部细节。想继续深入，可以依次阅读仓库中同章节的 建堆操作（解释为何整体建堆是 $O(n)$ 而非 $O(n\log n)$）、Top-K 问题（堆、排序、分治三种方案的复杂度对比），以及跨章节的 堆排序，从而将本节的堆操作与排序算法串联成完整的知识链。