前言：基于前文简单介绍了二叉树，现在我们根据完全二叉树来介绍堆这种数据结构。
一. 堆的定义与性质
堆是一种基于完全二叉树的有序数据结构，满足以下特性：
完全二叉树：除最后一层外，所有层都是满的，且最后一层节点靠左对齐。
性质：
最大堆（Max Heap）：每个父节点的值都大于或等于其子节点的值，根节点为最大值。
最小堆（Min Heap）：每个父节点的值都小于或等于其子节点的值，根节点为最小值。
存储方式：通常用数组表示堆，无需显式存储指针，通过下标计算节点关系：
父节点下标：parent(i) = (i-1)//2
左子节点下标：left(i) = 2i+1
右子节点下标：right(i) = 2i+2
示例：
最大堆数组：[9, 5, 6, 3, 2, 1]
对应二叉树结构：
9
/ \
5 6
/ \
3 2 二. 核心操作
堆的常见操作时间复杂度均为 O(log n)，因为完全二叉树的高度为 log₂n。
2.1插入节点（以最大堆为例）
步骤：
将新元素添加到数组末尾（完全二叉树的最后一个位置）。执行 ** 上浮（Upheap）** 操作：比较新元素与父节点，若新元素更大，则交换位置，重复直至满足堆性质。
示例：向 [9,5,6,3,2] 插入新元素 7
初始数组：[9,5,6,3,2,7]
上浮过程：7 的新父节点是 5（下标 1），7>5，交换 → [9,7,6,3,5,2]
7 的父节点是 2（下标 4），7>2，交换 → [9,5,6,3,7,2]最终堆：[9,7,6,3,5,2]
2.2 删除根节点（以最大堆为例）
步骤：
移除根节点（最大值），将最后一个元素移到根位置。执行 ** 下沉（Downheap）** 操作：比较当前节点与子节点，若子节点更大，则交换位置，重复直至满足堆性质。
示例：删除 [9,7,6,3,5,2] 的根节点 9
移除 9，末尾元素 2 移到根 → [2,7,6,3,5]
下沉过程：2 的子节点是 5（左子节点下标 3 是 3，右子节点下标 4 是 5，5 更大），交换 2 和 5 → [7,5,6,3,2]
2 的子节点是 7 和 6，7 更大，交换 2 和 7 → [7,2,6,3,5]最终堆：[7,5,6,3,2]
2.3堆化（Heapify）
将一个无序数组转换为堆，时间复杂度为 O(n)（从最后一个非叶子节点开始下沉）。
三、应用场景
3.1优先队列（Priority Queue）
特点：每次取出优先级最高的元素（最大堆取最大值，最小堆取最小值）。
实现：Java 的 PriorityQueue、Python 的 heapq 模块均基于堆实现。
场景：
任务调度（如操作系统中优先级高的进程优先执行）。
事件驱动系统（如按时间顺序处理事件）。
3.2堆排序（Heap Sort）
原理：
将数组构建为最大堆，根节点为最大值。
交换根节点与末尾元素，对前 n-1 个元素重新堆化，重复直至排序完成。
复杂度：时间 O (n log n)，空间 O (1)（原地排序）。
对比：无需额外空间，但稳定性差（相同元素顺序可能改变）。
3.3图算法优化
Dijkstra 算法：用最小堆优化顶点的最短路径查询，将时间复杂度从 O (n²) 降至 O ((m+n) log n)（m 为边数）。
Prim 算法：用最小堆选取最小生成树的边，优化稠密图的性能。
3.4Top K 问题
找数组中前 K 大（或小）的元素：若找前 K 大。
用最小堆存储当前最大的 K 个元素，堆顶为第 K 大元素。
若找前 K 小，用最大堆存储当前最小的 K 个元素，堆顶为第 K 小元素。
四、 进阶：斐波那契堆（Fibonacci Heap）
特点：
支持更高效的合并操作（均摊 O (1) 时间），适用于需要频繁合并优先队列的场景。
由多个最小堆树（Min-Heap Trees）组成，通过 “懒合并” 策略减少实际操作次数。
应用：高级图算法（如最短路径算法的进一步优化）。
数据结构研究（如并查集的路径压缩优化）。
五、堆 vs. 二叉搜索树
| 特性 | 堆 | 二叉搜索树 |
|---|---|---|
| 有序性 | 父节点与子节点有序（堆性质） | 中序遍历有序 |
| 查询最大值 / 最小值 | O (1)（根节点） | O (n)（最坏情况，需遍历） |
| 插入 / 删除复杂度 | O(log n) | O (log n)（平衡树） |
| 典型应用 | 优先队列、堆排序 | 字典、区间查询 |
六、总结
堆是一种高效的树形数据结构，核心在于通过完全二叉树和堆性质实现快速的最值访问与更新。掌握堆的基本操作（插入、删除、堆化）是理解优先队列、堆排序等算法的基础。若需处理大规模数据或高频合并操作，可进一步学习斐波那契堆、左偏树等进阶结构。