数据结构：堆 作者：马育民 • 2026-02-03 22:07 • 阅读：10005 # 介绍 **堆（Heap）** 是一种特殊的 **完全二叉树** 数据结构，通常用于实现优先队列和高效排序（如堆排序）。 # 什么是堆 设有 `n` 个元素的序列 `{K1，K2，... ，Kn}`，当且仅当满足下述关系之一时，称之为 **堆**： - 满足 $$K\_i <= K\_{2i}$$ 且 $$K\_i <= K\_{2i+1}$$ ，此时叫小根堆。 - 满足 $$K\_i>=K\_{2i}$$ 且 $$K\_i >= K\_{2i+1}$$ ，此时叫大根堆。 **提示：**其中 `2i` 和 `2i+1` 应不大于 `n` **提示：** 元素 $$K\_i$$、$$K\_{2i}$$、$$K\_{2i+1}$$ 的关系如下： [](https://www.malaoshi.top/upload/0/0/1GWwY22MlbY.png) # 结构性质 堆是一棵 **完全二叉树**。 - 除了最后一层，其他层的节点都是满的。 - 最后一层的节点都靠左排列。 - 这种结构非常适合用**数组**来存储。 # 分类 根据堆序性质，堆分为两种： - **大顶堆（大根堆，Max Heap）**：任意父节点的值 **大于等于** 其子节点的值。堆顶（根节点）是整个堆的**最大值**。 - **小顶堆（小根堆，Min Heap）**：任意父节点的值 **小于等于** 其子节点的值。堆顶（根节点）是整个堆的**最小值**。 如下图： [](https://www.malaoshi.top/upload/0/0/1GWwYvCxMA8.png) # 堆的存储 因为堆是完全二叉树，可以用数组存储： 假设数组索引从 **0** 开始，对于任意节点 `i`： - 父节点：`(i - 1) // 2` - 左孩子：`2 * i + 1` - 右孩子：`2 * i + 2` ### 例子 数组 `[10, 7, 6, 3, 5]` 表示的大顶堆： ```text 10 / \ 7 6 / \ 3 5 ``` # 构造堆 1. 首先找到最后一个节点的父节点，将父节点和2个子节点视为一个堆 2. 如果叶子节点的值大，就与父节点交换位置 3. 从后往前依次对每个堆进行步骤2的操作 ### 例子 原始数据为 `{4, 1, 3, 2, 16, 9, 10, 14, 8, 7}`，根据该数据建大顶堆 对应的完全二叉树如下图所示：  1. 最后一个节点为 `7`，其父节点为 `16`，从 `16` 这个节点开始构造最大堆； 2. 构造完毕之后，从后往前到下一个父节点 `2`，直到所有父节点都构造完毕。 [](https://www.malaoshi.top/upload/0/0/1GW2iYa1PVkL.png) # 时间复杂度 $$O(n)$$ ### 计算 用一棵高度为 **4 层**的满二叉树（n = 15），展示计算过程 ``` [A] 第 0 层 (根) / \ [B] [C] 第 1 层 / \ / \ [D] [E] [F] [G] 第 2 层 / \ / \ / \ / \ [H][I][J][K] [L][M] [N][O] 第 3 层 (叶子) ``` - 第 0 层：1 个节点 - 第 1 层：2 个节点 - 第 2 层：4 个节点 - 第 3 层：8 个节点（叶子，不移动） 1. **第 0 层（根）**： 要沉到第 3 层 → 最多走 **3 步** ``` [A] → 第1层 → 第2层 → 第3层 (3步) ``` 2. **第 1 层（B、C）**： 要沉到第 3 层 → 最多走 **2 步** ``` [B] → 第2层 → 第3层 (2步) [C] → 第2层 → 第3层 (2步) ``` 3. **第 2 层（D、E、F、G）**： 要沉到第 3 层 → 最多走 **1 步** ``` [D] → 第3层 (1步) [E] → 第3层 (1步) ... 共 4 个节点，各 1 步 ``` 4. **第 3 层（叶子）**： 已经在最底层 → 走 **0 步** 总步数 = 各层节点数 × 每节点步数 - 第 0 层：1 节点 × 3 步 = 3 - 第 1 层：2 节点 × 2 步 = 4 - 第 2 层：4 节点 × 1 步 = 4 - 第 3 层：8 节点 × 0 步 = 0 **总步数 = 3 + 4 + 4 = 11 步** n = 15，总步数 ≈ 11 ≈ n，所以建堆是 **O(n)**。 # 应用场景 堆能实现的功能，一般用数组也能实现，主要区别在插入、删除非最值元素的效率上 ： - 堆牺牲了 “全序性”，只保证堆顶是最值，换来 `插入 / 删除` 的 $$O (\log n)$$ 高效 - 有序数组是严格全序，但 `插入 / 删除` 要移动元素，效率仅 $$O (n)$$ ### 优先队列（Priority Queue） 堆最经典、最基础的应用： 需要按“优先级”而非“先来先服务”处理任务（每次取堆顶就是当前优先级最高/最低元素。） - 操作系统**进程调度**（高优先级进程优先执行） - 网络**数据包调度**（QoS 保证） - 事件驱动系统中的**事件优先级队列** --- ### 2. Top-K 问题（求前 K 大/前 K 小） 从海量数据中找出最大/最小的 K 个元素。 - 求**前 K 大**：用**小顶堆**，堆大小固定为 K，遍历数据时维护堆顶为当前第 K 大。 - 求**前 K 小**：用**大顶堆**，堆顶为当前第 K 小。 时间复杂度：$$O(n \log\_2K)$$，远优于排序 O(n log n)。 例子： - 热门榜单：热搜前 10、播放量前 100 - 日志/监控：找出访问量最高的 IP、错误最多的接口 --- ### 3. 堆排序（Heap Sort） 需要**稳定、原地、时间复杂度确定**的排序。 特点： - 时间复杂度：**O(n log n)**（最坏/平均/最好都一样） - 空间：可做到**原地排序**（O(1) 额外空间） 适用：对内存敏感、要求排序性能稳定的场景。 # 总结 - **堆 = 完全二叉树 + 堆序性质**。 - **大顶堆**：父 ≥ 子，堆顶最大。 - **小顶堆**：父 ≤ 子，堆顶最小。 - 核心操作是**堆化**，保证了高效的 O(log n) 调整。 原文出处：http://www.malaoshi.top/show_1GW2iX24hVDb.html