1 基本概念
1.1 堆的定义
堆是一种具有特定约束的树形结构，通常用于高效维护一组元素中的最大值或最小值。它强调的是局部有序而非全局有序，因此非常适合作为优先队列等抽象数据类型的底层实现。
1.1.1 堆序性质
堆序性质指的是每个父节点与其子节点之间必须满足特定的大小关系。对于最大堆，父节点不小于任一子节点；对于最小堆，父节点不大于任一子节点。由于这种约束只作用于相邻层级，堆并不保证同一层或整棵树内的元素完全排序。
1.1.2 完全二叉树性质
经典意义上的堆通常还要求其结构是一棵完全二叉树。也就是说，除最后一层外，其余各层节点都被填满，最后一层的节点则从左到右依次连续排列。这一结构保证了堆的高度较低，也便于用数组进行紧凑表示。
1.2 堆的类型
不同类型的堆，主要差别在于元素优先级的比较规则以及支持操作的侧重点。最常见的是最大堆与最小堆，此外还有兼顾两端查询能力的双端堆。
1.2.1 最大堆
最大堆中，根节点保存全体元素中的最大值。每次访问堆顶，都能直接取得当前集合里的最大元素，因此适合需要频繁提取最高优先级对象的场景。
1.2.2 最小堆
最小堆的根节点保存全体元素中的最小值。它常被用于需要不断获取最小代价、最早时间或最短距离的任务中，例如事件模拟、路径搜索和调度系统。
1.2.3 双端堆
双端堆是一类能够同时支持快速访问最小值和最大值的数据结构。与单端堆相比，它的组织方式更复杂，但在需要双向优先级管理的应用中更具灵活性。
1.3 堆与其他结构的区别
堆与其他常见数据结构相比，最显著的特点是只保证局部顺序，而不追求全面有序。因此，它在维护优先级方面很高效，但并不适合直接进行有序遍历或范围查找。
1.3.1 与二叉搜索树的区别
二叉搜索树强调左子树小于根、右子树大于根的全局搜索性质，因此中序遍历可以得到有序序列。堆则只要求父子之间满足优先级关系，不能直接用于快速查找任意键值，也不能保证遍历结果有序。
1.3.2 与普通数组的区别
普通数组仅提供线性存储，不自带优先级约束。若要从数组中找最大值或最小值，通常需要扫描全部元素；而堆通过维护结构性约束，使得堆顶即可代表当前最值，从而显著提高查询效率。
2 堆的表示方法
2.1 顺序存储
堆最常见的表示方式是数组顺序存储。由于堆具有完全二叉树的形态，数组能够较自然地对应树中各节点的位置，并减少指针开销。
2.1.1 数组下标与父子节点关系
在数组表示中，某个节点的位置可以通过下标直接推算其父节点和子节点的位置。这种映射使得上滤、下滤等操作都能在常数时间内定位相邻节点，从而提高实现效率。
2.1.2 1-based 与 0-based 表示
堆的数组实现常见两种下标习惯：一种从 1 开始编号，另一种从 0 开始编号。前者在计算父子关系时公式更简洁，后者更符合多数编程语言的数组习惯。二者本质一致，只是索引表达不同。
2.2 链式存储
链式存储通过节点和指针描述树结构，适合动态变化较频繁的树形场景。与数组相比，它更直观地反映父子关系，但在堆的应用中并不如顺序存储常见。
2.2.1 节点指针结构
链式堆通常由节点对象构成，每个节点保存数据以及指向左右子节点的指针，部分实现还会保存父节点指针。这样的结构便于局部调整和结构扩展，但需要额外内存来维护指针信息。
2.2.2 适用场景与局限
链式存储适合节点频繁插删且不便按数组重排的环境，不过在堆这种要求紧凑布局的数据结构中，其访问局部性较差，且实现复杂度通常高于数组方式，因此实际应用中较少采用。
2.3 隐式表示
堆还可以被看作完全二叉树在数组中的隐式映射。节点之间的父子关系不是显式存储，而是通过位置规则推导出来。
2.3.1 完全二叉树的层序映射
在层序遍历的顺序下，堆中的节点依次排列在数组中，先根后层、从左到右。由于完全二叉树的节点分布规则固定，这种层序映射无需额外结构信息即可还原树形关系。
2.3.2 存储空间优势
隐式表示避免了指针带来的额外开销，使存储更紧凑，也更利于缓存命中。对于规模较大的堆，这种空间与访问局部性的优势尤为明显。
3 堆的基本操作
3.1 插入元素
插入新元素时，通常先将其放到树的末尾，再通过调整恢复堆序性质。这个过程兼顾了结构完整性和优先级约束。
3.1.1 上滤过程
上滤是指新插入的元素从叶子位置向上比较，若违反堆序性质，就与父节点交换位置，直到满足条件或到达根节点。该过程可以有效将较大或较小的元素提升到合适位置。
3.1.2 时间复杂度分析
由于每次上滤最多经过堆的高度，插入操作的时间复杂度通常为对数级。对于完全二叉树，高度与节点总数之间近似呈对数关系，因此插入效率较高。
3.2 删除堆顶
删除堆顶通常意味着移除当前最值元素。为了保持树的完整结构，需要用最后一个叶子节点填补根位置，再执行调整。
3.2.1 下滤过程
下滤是指新的根节点不断与更合适的子节点比较，若不满足堆序，就与优先级更高的子节点交换位置，并继续向下移动。这样可以将破坏堆序的元素逐步推到合适层级。
3.2.2 重建堆顶性质
删除堆顶后，局部结构会暂时失去堆序，必须通过下滤恢复。完成这一过程后，整棵堆再次满足根节点代表最值、各子树保持局部有序的要求。
3.3 获取堆顶元素
堆顶元素是堆中最重要的访问对象，因为它直接对应当前的最大值或最小值。与普通线性结构相比，这种访问方式极为简洁。
3.3.1 最大值或最小值查询
在最大堆中，堆顶即为最大值；在最小堆中，堆顶即为最小值。因此，查询最值只需读取根节点，无需遍历整个结构。
3.3.2 常数时间性质
由于堆顶位置固定且无需调整，获取堆顶元素通常可在常数时间内完成。这也是堆在实时优先级管理中备受重视的原因之一。
3.4 修改元素
当某个元素的键值发生变化时，需要根据变化方向决定调整方式，以保持堆序性质不被破坏。
3.4.1 增大键值
在最大堆中，若某个节点键值增大，它可能需要向上移动以满足父节点不小于子节点的要求；在最小堆中，增大键值通常会导致该节点下移。具体方向取决于堆类型与变化后的相对顺序。
3.4.2 减小键值
与增大相反，减小键值在最大堆中往往会使节点下移，而在最小堆中可能促使其上移。修改操作通常需要局部比较并沿树调整，直到恢复堆序为止。
4 堆的构建
4.1 自底向上建堆
自底向上建堆是较为高效的构造方法，常用于将一个无序数组快速整理成堆。它从底层非叶节点开始逐步调整，直到根节点。
4.1.1 从最后一个非叶节点开始调整
由于叶节点天然满足堆序性质，构建时只需对最后一个非叶节点及其以上节点逐个执行下滤。这样可以先修复局部子树，再向上合并成整体有序结构。
4.1.2 线性时间建堆证明
尽管单次下滤可能达到对数时间，但越靠近底层的节点可移动距离越短，整体总代价并不会简单相加为对数级乘以节点数。综合各层节点数量与调整长度，可证明建堆总复杂度为线性级别。
4.2 自顶向下建堆
自顶向下建堆通常通过逐个插入元素实现。每加入一个元素，就执行上滤，使当前前缀保持堆性质。
4.2.1 逐个插入法
这种方法实现直观，适合动态到达数据的场景。每次插入后重新调整局部位置，最终形成完整堆，但构建效率相对较低。
4.2.2 与线性建堆的效率比较
逐个插入法的总耗时通常高于自底向上方法，尤其在数据量较大时差异明显。前者更适用于在线处理，后者则更适合批量初始化。
4.3 堆化过程
堆化是把一个任意二叉树局部或整体调整为堆的过程。它既可以用于构建，也可以用于插入、删除后的修复。
4.3.1 局部调整
堆化通常从发生变化的位置开始，通过上滤或下滤修正局部结构。只要局部恢复了正确顺序，堆序就可以逐步扩展到更大范围。
4.3.2 全局恢复堆序
当每个受影响的子树都被正确调整后，整棵树便重新满足堆的定义。换言之，堆化的目标就是将局部失衡重新整合为整体有序。
5 堆的算法应用
5.1 堆排序
堆排序是一种基于堆结构的比较排序方法，通常通过先建堆，再反复取出堆顶元素完成排序。
5.1.1 建堆阶段
排序开始时，先将原始序列转换为最大堆或最小堆。这样，堆顶就代表当前序列中的极值，便于后续逐步输出结果。
5.1.2 反复取堆顶阶段
每次取出堆顶后，将末尾元素移到根部并重新下滤。重复这一过程，便可按特定顺序依次得到全部元素。
5.1.3 时间与空间复杂度
堆排序的时间复杂度通常为对数级调整与线性建堆的组合，整体表现稳定；空间上可在原数组内原地完成，不需要额外大量存储。
5.2 优先队列
优先队列是一种按优先级而非插入顺序处理元素的抽象结构，而堆正是其最常见实现方式。
5.2.1 任务调度
在任务调度中，系统常需要优先处理紧急程度更高或截止时间更早的任务。堆能够快速找出当前最高优先级对象，因此非常适合动态任务管理。
5.2.2 事件管理
离散事件模拟中，未来将发生的事件往往按时间先后排列。使用最小堆可以迅速取得最早发生的事件，从而按时间轴推进模拟过程。
5.3 图算法中的应用
堆在图论算法里十分常见，主要用于维护候选边或候选顶点的优先级。它能显著减少重复扫描，提高搜索效率。
5.3.1 Dijkstra 算法
在单源最短路径问题中，最小堆常用于保存尚未确定最短距离的顶点。每次取出当前距离最小的顶点进行扩展，可加速路径松弛过程。
5.3.2 Prim 算法
Prim 算法构造最小生成树时，需要不断选择连接树与非树部分的最小代价边。优先队列能够帮助快速筛选当前最优边，从而提升整体效率。
5.4 数据流处理
对于持续到达的数据，堆可以帮助系统在不保存全部历史的情况下维护关键统计信息。
5.4.1 动态中位数维护
动态中位数问题常通过两个堆协同解决：一个维护较小的一半数据，一个维护较大的一半数据。这样可以在数据持续加入时迅速更新中位数。
5.4.2 Top-K 问题
Top-K 问题关注的是当前最大的或最小的前 K 个元素。利用大小固定的堆，可以在流式环境中高效筛选出所需结果，而无需对全部数据排序。
6 堆的性质与分析
6.1 完全二叉树的高度性质
堆之所以高效，与完全二叉树的结构密切相关。其高度增长缓慢，使很多操作只需少量比较即可完成。
6.1.1 节点数量与层数关系
在完全二叉树中，随着层数增加，节点数量按近似倍增的方式增长。因此，给定节点总数时，其层数不会过多，这直接限制了堆的高度。
6.1.2 高度的对数级结论
当节点数量为 n 时，堆的高度通常与 log n 成正比。也正因为如此，沿树向上或向下的调整操作一般只需对数时间。
6.2 操作复杂度
堆在设计上追求的是优先级操作的高效性，尤其是插入、删除和建堆这几类核心动作。
6.2.1 插入与删除复杂度
插入和删除堆顶时，元素最多沿树高方向移动一次，因此复杂度通常为对数级。与线性扫描相比，这种效率优势在大规模数据中十分明显。
6.2.2 建堆复杂度
自底向上的建堆方法能够在线性时间内完成，这使得堆适合作为批量初始化结构。相比逐个插入方式，它更适用于离线构造。
6.3 正确性证明
堆的正确性建立在局部比较和结构完整性之上。只要每次操作都能恢复必要约束，堆就能长期保持有效。
6.3.1 堆序维护
每一次插入、删除或修改，都必须确保父子关系重新满足堆序。这种维护是堆正确运行的核心，任何一次未完成的修复都可能破坏后续操作结果。
6.3.2 归纳证明思路
堆相关算法常采用归纳法证明正确性：先证明单个节点或局部子树满足性质，再证明当局部步骤重复执行时，整体结构也将逐步恢复为合法堆。
7 变体与扩展
7.1 d 叉堆
d 叉堆将每个节点的子节点数量从二个扩展为 d 个。它通过增大分支因子，改变了树高与每层比较次数之间的平衡。
7.1.1 节点分支数扩展
与二叉堆相比，d 叉堆中每个节点可以拥有更多子节点，因此树的高度更低。不过，单次调整时需要检查的子节点也更多。
7.1.2 复杂度变化
d 叉堆在某些场景下可以减少树高相关的移动成本，但会增加每一层的比较代价。具体优劣取决于操作类型与数据规模。
7.2 左偏堆
左偏堆是一种适合高效合并的堆结构，常用于需要频繁合并两个优先队列的情况。
7.2.1 合并操作
左偏堆的核心特征之一是支持快速合并。两个堆可以通过递归地比较根节点并调整子树结构来完成合并，这使其在合并密集型任务中很有吸引力。
7.2.2 应用场景
当系统需要不断把多个小队列合并为一个大队列时，左偏堆往往比普通二叉堆更合适。它常见于一些事件模拟和动态集合管理问题中。
7.3 斐波那契堆
斐波那契堆是一种更为松散的堆结构，强调某些操作的摊还效率，尤其在图算法中表现突出。
7.3.1 松散结构特点
与传统堆严格维护结构不同，斐波那契堆允许更宽松的树形组织方式，把部分调整推迟到后续操作中处理，以换取某些关键操作的更低摊还复杂度。
7.3.2 图算法中的高效应用
在需要大量减小键值的图算法里，斐波那契堆能显著降低相关代价，因此在理论分析中常被用于展示更优的渐进复杂度。
8 相关概念
8.1 堆与树
堆本质上属于树结构的一种，因此理解树的基本概念有助于把握堆的组织方式与性质约束。
8.1.1 二叉树基础
二叉树是每个节点最多拥有两个子节点的树形结构。堆通常建立在二叉树框架上，因此其节点、层级和递归特征都与二叉树密切相关。
8.1.2 完全二叉树
完全二叉树是堆得以高效存储和操作的重要前提。它保证节点分布紧凑，使数组映射与对数级调整成为可能。
8.2 堆与排序
堆在排序理论中占有一席之地，尤其在比较排序方法中，常被用作构造稳定优先级流程的工具。
8.2.1 比较排序中的位置
作为比较排序的一个代表性实现，堆排序不依赖额外分治划分，而是利用堆顶反复输出极值。它在最坏情况下仍能保持较稳定的时间表现。
8.2.2 与快速排序的对比
与快速排序相比，堆排序通常具有更稳定的最坏情况复杂度，但局部交换与缓存友好性往往不如快速排序。两者各有适用条件，常根据性能侧重点选择。
8.3 堆与优先级管理
堆最直接的价值体现在优先级管理上。它能够在动态变化的数据集合中，持续提供最重要元素的快速访问。
8.3.1 最值维护
无论是最大值还是最小值，堆都能在较低代价下持续维护当前极值。这使其适合处理实时更新的目标集合。
8.3.2 动态选择问题
在许多动态选择问题中，系统需要不断从候选集中挑出最合适的对象。堆通过高效的插入、删除和查询机制，为这类问题提供了通用而可靠的实现基础。