堆

在数据结构与算法中，堆（Heap） 是一种基于完全二叉树的高效数据结构，其核心价值在于通过严格的结构约束和序性规则，实现对“极值元素”（最大值或最小值）的快速访问、插入和删除。以下从本质、实现细节、核心操作、应用场景等方面进行深度解析：

一、堆的本质：双重约束的完全二叉树

堆的定义包含两个不可分割的条件，缺一不可：

1. 结构性约束：完全二叉树

完全二叉树的特点是：

• 除最后一层外，所有层的节点均被完全填满（无空缺）；
• 最后一层的节点从左到右连续排列，不允许中间有空缺（即若有节点缺失，只能在右侧）。

这种结构的优势是可以用数组紧凑存储（无需链表的指针开销），且节点间的父子关系可通过简单的数学公式直接计算（见下文“存储映射”）。

2. 序性约束：父节点与子节点的大小关系

根据父节点与子节点的大小规则，堆分为两种：

• 大顶堆（Max Heap）：任意节点的值 ≥ 其左右子节点的值（根节点是整个堆的最大值）；
• 小顶堆（Min Heap）：任意节点的值 ≤ 其左右子节点的值（根节点是整个堆的最小值）。

关键注意：堆仅约束“父节点与子节点”的关系，不约束左右子节点的大小（例如大顶堆中左子节点可大于或小于右子节点）。

二、堆的存储：数组与完全二叉树的映射

由于堆是完全二叉树，无需用链表存储，而是通过数组直接映射，映射规则如下（假设数组索引从 0 开始）：

节点角色	索引计算公式（当前节点索引为 i）
左子节点索引	2*i + 1
右子节点索引	2*i + 2
父节点索引	(i - 1) // 2（整数除法）

示例：大顶堆 [10, 5, 7, 4, 1, 3] 的数组与树结构对应关系：

      10 (i=0)
     /   \
  5(i=1)  7(i=2)
   / \    /
4(i=3) 1(i=4) 3(i=5)

三、堆的核心操作：维持序性的底层逻辑

堆的所有操作都围绕“在结构变化后快速恢复堆序性”展开，核心操作依赖两个基础调整函数：向上调整 和向下调整。

1. 基础调整函数

（1）向上调整

适用场景：新元素插入堆尾后，可能破坏堆序性（如大顶堆中新增元素大于父节点），需从该元素开始向上“冒泡”，直到满足堆序。

步骤（以大顶堆为例）：

1. 设新元素索引为 i，其父节点索引为 parent = (i-1) // 2；
2. 若 heap[i] > heap[parent]，交换两者，更新 i = parent；
3. 重复步骤 1-2，直到 i = 0（根节点）或 heap[i] ≤ heap[parent]。

时间复杂度：O(log n)（最多遍历树的高度，完全二叉树高度为 log₂n）。

（2）向下调整

适用场景：堆顶元素被替换（如删除堆顶后用尾元素填充），可能破坏堆序性，需从根节点开始向下“沉底”，直到满足堆序。

步骤（以大顶堆为例）：

1. 设当前节点索引为 i，左子节点 left = 2*i + 1，右子节点 right = 2*i + 2；
2. 找出 i、left、right 中值最大的节点，记为 max_idx（若子节点不存在则忽略）；
3. 若 max_idx ≠ i（当前节点不是最大值），交换 i 和 max_idx，更新 i = max_idx；
4. 重复步骤 1-3，直到 i 为叶子节点（无有效子节点）或满足堆序。

时间复杂度：O(log n)（同向上调整，受树高限制）。

2. 插入元素

目标：在堆中添加新元素，同时维持堆的结构和序性。

步骤：

1. 将新元素追加到数组末尾（保证完全二叉树的结构完整性）；
2. 对新元素执行向上调整，恢复堆序性。

示例：向大顶堆 [10,5,7,4,1] 插入 6：

• 追加后数组为 [10,5,7,4,1,6]，新元素索引 i=5；
• 父节点 parent=(5-1)//2=2（值为 7），6 < 7，无需交换，插入完成。

3. 删除堆顶元素

目标：移除堆顶（最大值/最小值），同时维持堆的结构和序性。

步骤：

1. 保存堆顶元素的值（作为返回结果）；
2. 将数组末尾元素移到堆顶位置（覆盖原堆顶），并删除末尾元素（保证结构完整性）；
3. 对新堆顶执行向下调整，恢复堆序性。

示例：删除大顶堆 [10,5,7,4,1,6] 的堆顶：

• 保存堆顶 10，用尾元素 6 覆盖堆顶，数组变为 [6,5,7,4,1]；
• 对 i=0 执行向下调整：左子 5、右子 7，最大为 7（i=2），交换得 [7,5,6,4,1]；
• 更新 i=2，左子 1（右子不存在），6 > 1，停止。最终堆为 [7,5,6,4,1]。

4. 构建堆

目标：将无序数组转换为堆（大顶堆或小顶堆）。

核心思路：从最后一个非叶子节点开始，依次向前对每个节点执行向下调整（叶子节点无需调整，因无子女）。

• 最后一个非叶子节点的索引：n//2 - 1（n 为数组长度）。

步骤（以大顶堆为例）：

1. 初始化 i = n//2 - 1；
2. 对 i 执行向下调整，然后 i -= 1；
3. 重复步骤 2，直到 i = 0（根节点调整完成）。

示例：将 [3,1,4,2,5] 构建为大顶堆：

• n=5，最后一个非叶子节点索引 5//2 -1 =1（值为 1）；
• 对 i=1 调整：左子 2、右子 5，最大为 5（i=4），交换得 [3,5,4,2,1]；
• 对 i=0 调整：左子 5、右子 4，最大为 5（i=1），交换得 [5,3,4,2,1]；
• 对 i=1 再次调整（因交换后可能破坏子堆序）：左子 2、右子 1，3 已最大，完成构建。

时间复杂度：O(n)（数学推导证明：所有节点的调整次数总和为 O(n)，而非 O(n log n)）。

四、堆的时间复杂度总结

操作	时间复杂度	说明
访问堆顶元素	O(1)	直接访问数组首元素
插入元素	O(log n)	向上调整最多遍历树高
删除堆顶元素	O(log n)	向下调整最多遍历树高
构建堆	O(n)	线性复杂度，优于逐个插入

五、堆的典型应用场景

1. 优先队列
   优先队列的核心需求是“每次取出优先级最高的元素”，堆是其最优实现：

   • 入队（插入）：O(log n)；
   • 出队（取最高优先级）：O(log n)。
     应用：任务调度（高优先级任务先执行）、Dijkstra 最短路径算法（快速获取当前最短边）。

2. 堆排序
   利用大顶堆的特性排序，步骤：

   1. 将数组构建为大顶堆（O(n)）；
   2. 反复将堆顶（最大值）与末尾元素交换，然后对前 n-1 个元素执行向下调整（O(n log n)）。
      时间复杂度 O(n log n)，但不稳定（相等元素可能改变相对顺序）。

3. Top K 问题
   求海量数据中最大的 K 个元素（或最小的 K 个元素）：

   • 用小顶堆存储 K 个候选元素，遍历数据时，若新元素大于堆顶，则替换堆顶并调整（O(log K)）；
   • 整体复杂度 O(n log K)，远优于全量排序（O(n log n)）。

六、堆的局限性

• 不支持随机访问：无法像数组一样通过索引直接访问任意元素；
• 不支持范围查询：难以高效查找“值在 [a,b] 之间的元素”；
• 调整操作依赖树高：若堆退化为非完全二叉树（如频繁删除导致结构松散），性能会下降。