数据结构:堆 作者:马育民 • 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://malaoshi.top/show_1GW2iX24hVDb.html