什么是堆？¶
想象你有一堆文件，想优先处理最重要的（比如紧急文件），或者优先处理最不重要的（比如垃圾文件）。这时候，“堆”就像一个特殊的“容器”，能让你快速拿到最大或最小的那个元素。
堆其实是一种特殊的完全二叉树，它的核心特点是：每个父节点的值都满足某种规则（小于或等于/大于或等于子节点）。这种规则让堆能高效地获取“最大”或“最小”的元素，就像一个“优先队列”。
堆的结构基础：完全二叉树¶
堆的底层是一棵完全二叉树。完全二叉树有什么特点呢？
- 每一层都填满了节点，除了最后一层可能不填满；
- 最后一层的节点从左到右依次排列，没有“跳过”。
举个例子：
1
/ \
3 2
/ \ /
6 4 5
这是一个完全二叉树，每一层都尽量填满，最后一层（第3层）有3个节点（6、4、5），从左到右排列。
最小堆 vs 最大堆¶
堆有两种类型，核心区别在于父节点和子节点的大小关系：
最小堆（Min-Heap）¶
- 规则：父节点的值 小于或等于 所有子节点的值。
- 堆顶：最小的元素（根节点）。
例子（数组表示）：
最小堆用数组存储时，数组的索引对应节点位置，规则是：
- 左子节点索引 = 2×父节点索引 + 1
- 右子节点索引 = 2×父节点索引 + 2
- 父节点索引 = (子节点索引 - 1) // 2
比如数组 [1, 3, 2, 6, 4, 5] 表示的最小堆：
- 堆顶（索引0）是1（最小）；
- 1的左子节点（索引1）是3，右子节点（索引2）是2，满足 1 ≤ 3 且 1 ≤ 2；
- 3的左子节点（索引3）是6，右子节点（索引4）是4，满足 3 ≤ 6 且 3 ≤ 4；
- 2的左子节点（索引5）是5，满足 2 ≤ 5。
最大堆（Max-Heap）¶
- 规则：父节点的值 大于或等于 所有子节点的值。
- 堆顶：最大的元素（根节点）。
例子（数组表示）：
数组 [10, 5, 8, 3, 2, 1] 表示的最大堆：
- 堆顶（索引0）是10（最大）；
- 10的左子节点（索引1）是5，右子节点（索引2）是8，满足 10 ≥ 5 且 10 ≥ 8；
- 5的左子节点（索引3）是3，右子节点（索引4）是2，满足 5 ≥ 3 且 5 ≥ 2；
- 8的左子节点（索引5）是1，满足 8 ≥ 1。
堆的数组表示与索引关系¶
堆最常用数组存储，因为完全二叉树的结构天然适合数组索引。记住这个“父子索引公式”：
- 对于数组中索引为 i 的节点：
- 左子节点：2*i + 1
- 右子节点：2*i + 2
- 父节点：(i - 1) // 2（整数除法）
比如数组 [1, 3, 2, 6, 4, 5]（最小堆）：
- 节点1（索引0）的子节点是3（索引1）和2（索引2）；
- 节点3（索引1）的子节点是6（索引3）和4（索引4）；
- 节点2（索引2）的子节点是5（索引5）。
堆的基本操作：插入与删除¶
堆的核心优势是插入和删除操作效率极高（时间复杂度 O(log n)），因为堆的高度是 log n（n 为元素个数）。
1. 插入操作（以最小堆为例）¶
步骤：
1. 把新元素放到数组的末尾（即最后一个位置）；
2. 从新元素开始，向上“上浮”（上滤）：比较该元素与父节点的值，如果新元素更小（最小堆），则交换，直到父节点更小或到达堆顶。
例子：
原最小堆数组：[1, 3, 2, 6, 4, 5]（堆顶1）
插入新元素 0：
- 先放到末尾：数组变成 [1, 3, 2, 6, 4, 5, 0]；
- 上浮：0 的父节点是索引3（值6），0 < 6，交换 → [1, 3, 2, 0, 4, 5, 6]；
- 继续上浮：0 的父节点是索引1（值3），0 < 3，交换 → [1, 0, 2, 3, 4, 5, 6]；
- 继续上浮：0 的父节点是索引0（值1），0 < 1，交换 → [0, 1, 2, 3, 4, 5, 6]。
现在数组满足最小堆性质，插入完成。
2. 删除操作（以最小堆为例）¶
步骤：
1. 删除堆顶元素（最小元素）；
2. 把数组最后一个元素放到堆顶；
3. 从堆顶开始，向下“下沉”（下滤）：比较该元素与子节点的值，如果子节点更小（最小堆），则交换，直到子节点更大或到达叶子节点。
例子：
原最小堆数组：[0, 1, 2, 3, 4, 5, 6]（堆顶0）
删除堆顶元素：
- 先删除0，数组变成 [1, 2, 3, 4, 5, 6]；
- 把最后一个元素6放到堆顶：数组变成 [6, 2, 3, 4, 5, 6]？不对，原数组长度是7，删除后长度6，最后一个元素是6（索引5），放到堆顶（索引0）：[6, 2, 3, 4, 5, 6]？
- 下沉：6 的子节点是2（索引1）和3（索引2），最小子节点是2，6 > 2，交换 → [2, 6, 3, 4, 5, 6]；
- 继续下沉：6 的子节点是4（索引3）和5（索引4），最小子节点是4，6 > 4，交换 → [2, 4, 3, 6, 5, 6]；
- 继续下沉：6 的子节点是5（索引5），6 > 5，交换 → [2, 4, 3, 5, 6, 6]；
- 此时堆顶2，子节点4（4>2）和3（3>2），满足最小堆，删除完成。
堆的应用场景¶
堆最经典的应用是优先队列，即“每次取出优先级最高（最大/最小）的元素”。以下是常见场景：
1. 优先队列（任务调度）¶
- 比如服务器处理任务，按优先级（紧急程度）排序，用最大堆每次取最高优先级任务；
- 医院急诊室按病情紧急度排序，用最大堆快速取出最紧急的病人。
2. 找第k大的数¶
- 用最小堆维护前k大的数，堆顶就是第k大的数。例如找第3大的数：
- 遍历数组，保持堆大小为3，新元素比堆顶大则替换并调整堆，最后堆顶就是第3大的数。
3. 哈夫曼编码（压缩算法）¶
- 用最小堆合并频率最低的两个节点，构建哈夫曼树，用于数据压缩。
总结¶
堆是一种基于完全二叉树的特殊结构，核心是“父节点与子节点的大小关系”。最小堆和最大堆分别用于快速获取最小或最大元素，通过插入（上浮）和删除（下沉）操作维护堆的性质。堆的 O(log n) 操作效率使其成为优先队列、第k大元素等问题的首选数据结构。
对于初学者，建议从数组表示和插入/删除步骤入手，通过具体例子（如上文的插入删除过程）理解堆的逻辑，再逐步应用到实际问题中。堆的应用广泛且实用，掌握它能极大提升算法效率哦！