一、堆的基本概念
堆（Heap）是一棵完全二叉树（除最后一层外每层都是满的，且最后一层的节点从左到右连续排列），且满足堆序性质：对于最大堆（Max-Heap），任意节点的值大于等于其所有子节点的值；对于最小堆（Min-Heap），任意节点的值小于等于其所有子节点的值。
堆的完全二叉树性质使其可以自然地使用数组存储，无需显式的指针。对于索引为i的节点（0基）：父节点索引为(i-1)/2；左子节点索引为2i+1；右子节点索引为2i+2。如果某节点的索引i满足i ≥ n/2（n为堆大小），则该节点是叶子节点。
堆不是为查找任意元素而设计的——它只保证从根节点到任意叶子节点的路径上有序，不保证兄弟节点之间或不同分支之间的大小关系。堆专为“快速获取最值”而设计：获取最大值/最小值为O(1)，插入为O(log N)，删除最值为O(log N)。
二、二叉堆的操作
插入（Insert / Offer）：将新元素添加到数组末尾（保持完全二叉树性质），然后执行“上浮”（Sift Up / Bubble Up / Percolate Up）操作——新元素与其父节点比较，如果违反堆序（如在最小堆中新元素小于父节点），则交换；重复直到满足堆序或到达根。
void offer(int value, int[] heap, int size) { |
插入的时间复杂度为O(log N)，因为上浮操作最多沿树的高度进行——在完全二叉树中高度为⌊log₂N⌋。有趣的是，如果插入的随机元素最终在堆中的位置是随机的，上浮的期望次数仅为常数（约2.6次，通过调和级数分析可得），因为大多数元素最终落在较底层。
删除最值（Poll / Extract Min）：取出根节点（最值），将数组最后一个元素移到根位置（保持完全二叉树性质），然后执行“下沉”（Sift Down / Percolate Down）操作——从根开始，将其与两个子节点比较，如果违反堆序，与更小（最小堆）或更大（最大堆）的子节点交换；重复直到满足堆序或到达叶子。
int poll(int[] heap, int size) { |
建堆（Build Heap）：给定一个无序数组，如何在线性时间内将其转化为堆？方法是从最后一个非叶子节点开始（索引为n/2 - 1），逆序对每个节点执行下沉操作。该方法的时间复杂度为O(N)而非O(N log N)，证明思路是：对于高度为h的满二叉堆，第k层的节点下沉最多h-k次，求和得到O(N)。具体而言，第0层（最底层叶子）有N/2个节点，下沉0次；第1层有N/4个节点，最多下沉1次；…；第h层（根）有1个节点，最多下沉h次。总和为Σ(k=0到h) (k × N/2^(k+1)) < N × Σ(k/2^(k+1)) = N × 1 = O(N)。
void buildHeap(int[] arr) { |
三、Java PriorityQueue源码分析
Java的java.util.PriorityQueue是一个基于二叉堆的无界优先队列，默认是最小堆（可通过Comparator自定义）。以下是核心源码要点：
存储结构：使用Object[] queue数组存储元素。默认初始容量为11（一个不太常见的质数选择，可能源于历史原因）。
插入（offer）：如果容量不足，先扩容（如果当前容量<64，扩容为2倍+2；否则扩容为1.5倍）。然后将新元素放在数组末尾，执行siftUp。
删除最值（poll）：取出queue[0]，将数组最后一个元素移到queue[0]，执行siftDown。
堆化构造函数：如果通过PriorityQueue(Collection)构造并传入一个无序集合，使用heapify()方法（等价于buildHeap，从size/2处开始下沉）在O(N)时间内建堆。如果传入的是SortedSet或其他PriorityQueue，可以直接复制数组（已经有序）。
索引查找：PriorityQueue不提供任意元素索引查找——remove(Object)通过线性扫描找到元素索引，时间复杂度O(N)。如果需要O(log N)的任意元素删除，需要使用更复杂的数据结构（如带HashMap索引的堆，也称为Indexed Priority Queue）。
线程安全：PriorityQueue不是线程安全的。并发场景使用PriorityBlockingQueue，其内部使用ReentrantLock保证线程安全，并提供阻塞操作（take()在队列为空时阻塞等待）。
四、d叉堆
二叉堆推广到d叉堆（d-ary Heap）：每个节点有d个子节点。对于索引i（0基）的节点，其子节点索引为d*i+1, d*i+2, ..., d*i+d；其父节点索引为(i-1)/d。
d叉堆的权衡：d越大，树的高度越低（log_d N vs log_2 N），下沉操作虽然比较次数增加（每层需比较d个子节点），但树的层数减少，且下沉重在CPU缓存友好性上更好（因为树更宽、更浅，访问的节点内存更连续）。在实践中，d=4（四叉堆）在许多基准测试中表现优于二叉堆，因为现代CPU的缓存行可以容纳更多的子节点，且分支预测在面对4路比较时表现不错。Java的PriorityQueue使用二叉堆（d=2），是一种稳妥的设计。
五、斐波那契堆
斐波那契堆（Fibonacci Heap）是一种理论优美、实现复杂的堆结构，它通过懒合并（Lazy Union）和摊还分析（Amortized Analysis）在许多操作上达到了极优的摊还时间复杂度。
斐波那契堆的关键特性：由一个最小堆有序的树集合（森林）构成，每棵树满足最小堆性质但不一定是二叉树。维护一个指向最小节点的指针。所有合并（union）、插入等操作都是“懒”的——仅仅是连接到根链表中，不立即整理结构。只有当执行“提取最小值”（Extract-Min）操作时，才执行合并（Consolidate）——将度数相同的树合并，使根链表中的树度数互不相同。合并后，森林中树的数量最多为log_φ N（φ为黄金比例），这也是“斐波那契”名称的来源（树的大小呈斐波那契数列增长）。
斐波那契堆的摊还时间复杂度：
| 操作 | 二叉堆 | 斐波那契堆 |
|---|---|---|
| 插入 | O(log N) | O(1) |
| 查看最小 | O(1) | O(1) |
| 提取最小 | O(log N) | O(log N) |
| 合并 | O(N) | O(1) |
| 减小键值 | O(log N) | O(1) |
“减小键值”（Decrease-Key）的O(1)摊还时间是斐波那契堆最独特的优势。当图中边数远大于顶点数时（如稠密图），Dijkstra算法使用斐波那契堆的时间复杂度从O((V+E) log V)降为O(V log V + E)，其中E次Decrease-Key操作各自O(1)。但在实践中，由于斐波那契堆的常数因子很大（维护复杂的指针结构和级联剪切），二叉堆在大多数实际规模的图上反而更快。只有在极其庞大的图上（数千万顶点，数十亿边），斐波那契堆的理论优势才能体现。
六、配对堆
配对堆（Pairing Heap）是实践中性能最好的堆实现之一。它像是斐波那契堆的“简化实用版”——同样维护一组堆有序树的集合，但合并策略更简单。
配对堆的核心操作是两趟合并（Two-Pass Merge）：提取最小值后，移除根节点，将其所有子树的根组成一个列表；从左到右将相邻的树两两配对合并（第一趟），然后从右到左将合并结果逐一合并（第二趟）。配对堆的所有操作在实践中非常快，尽管其摊还时间复杂度尚未被完全证明（Extract-Min是否确实是O(log N)摊还仍是一个开放问题）。
配对堆的实现比斐波那契堆简单得多（通常只需要几十行代码），在实践中性能经常超越二叉堆。许多算法竞赛选手和性能敏感的应用使用配对堆作为优先队列实现。
七、堆的经典应用
Top K问题：从海量数据中找出最大/最小的K个元素。维护一个大小为K的最小堆（找最大的K个）或最大堆（找最小的K个）。遍历所有数据，如果当前元素大于（或小于）堆顶，则替换堆顶并下沉。时间复杂度O(N log K)，空间复杂度O(K)。当K << N时，这个算法远优于全量排序的O(N log N)。
多路归并：合并K个有序序列为一个有序序列。将所有序列的第一个元素（最小元素候选）加入最小堆。每次从堆中取出最小值，将其所属序列的下一个元素加入堆。每个元素经历一次入堆和一次出堆，总时间复杂度O(N log K)。这在外排序的最后阶段——将多个有序的归并段合并为最终有序输出——是核心操作。
Huffman编码建树：使用最小堆每次取出频率最小的两个节点合并（贪心算法）。
中位数维护（Median Maintenance）：使用两个堆——一个最大堆存储较小的一半元素，一个最小堆存储较大的一半元素。插入新元素时，根据大小选择放入哪个堆，然后调整两个堆的大小使其平衡（大小相差不超过1）。在任何时刻，中位数要么是最大堆的堆顶（如果总数为奇数），要么是两个堆顶的平均值（如果总数为偶数）。每个操作O(log N)，随时可以O(1)获取中位数。
调度系统：操作系统的任务调度器使用优先队列按照优先级调度进程。Linux的CFS（完全公平调度器）使用红黑树按vruntime排序。定时器管理使用最小堆按触发时间排序——取出堆顶，如果触发时间未到则睡眠到该时间，否则执行定时器回调。
八、面试常见追问
问题一：堆排序中为什么要从后往前建堆而非从前往后？
从后往前建堆（Floyd算法）利用了下沉操作的特性——从最后一个非叶子节点开始，保证在处理每个节点时，其子树已经是合法的堆，因此只需一次下沉即可使当前子树成为堆。这得到了O(N)的优秀建堆时间。如果从前往后建堆（逐个插入），需要N次插入操作，每次O(log N)，总时间复杂度为O(N log N)。两种方法的结果相同（虽然具体的数值排列可能不同），但Floyd建堆在常数因子和渐近意义上都更优。
问题二：为什么PriorityQueue不支持索引访问任意元素？
二叉堆的结构本质上是一个偏序而非全序——它只保证父子之间的序关系，不保证兄弟之间或任意两点之间的大小关系。要支持O(log N)的索引访问（如decrease-key），需要在堆中的元素移动时维护一个额外的HashMap，记录每个元素在数组中的当前位置。这种结构通常称为Indexed Priority Queue或Addressable Priority Queue。Java标准库为了保持API的简洁性，选择了简单的二叉堆实现。需要decrease-key的场景可以使用斐波那契堆的第三方实现或者自建带索引的堆。
问题三：斐波那契堆的decrease-key为什么要使用级联剪切（Cascading Cut）？
级联剪切是为了维护“任何节点的度数不能过大”这一性质，从而保证Extract-Min时Consolidation的效率。当一个节点失去一个子节点时，它被标记（Mark）；当它失去第二个子节点时，它被从其父节点剪切并插入根链表，同时递归检查其父节点。这个过程确保任意节点的度数（子节点数量）与其子树的大小之间存在对数关系（一个度数为k的节点，其子树至少包含F_{k+2}个元素，F为斐波那契数）。没有级联剪切，Consolidate操作后根链表中的树数量无法保证为O(log N)，Extract-Min的摊还时间复杂度将退化为O(N)。
