堆（Heap）

在计算机数据结构中，堆（Heap） 是一种基于完全二叉树的数据结构，其核心特性是「父节点与子节点之间的大小关系具有严格规则」，且通常通过数组实现（而非指针链接的树结构）。堆的设计目标是高效地获取和维护集合中的「极值」（最大值或最小值）。

一、堆的核心特性

1. 结构特性：堆是一棵完全二叉树（除最后一层外，每一层都被完全填满，最后一层的节点从左到右依次排列）。
2. 值特性：
   • 若为最大堆（Max Heap）：每个父节点的值 ≥ 其左右子节点的值（根节点是整个堆的最大值）。
   • 若为最小堆（Min Heap）：每个父节点的值 ≤ 其左右子节点的值（根节点是整个堆的最小值）。

二、堆的存储结构

由于堆是完全二叉树，可直接用数组高效存储（无需指针），通过索引计算父子节点位置：

• 设数组索引从 0 开始，对于任意节点 i：
  • 左子节点索引：2i + 1
  • 右子节点索引：2i + 2
  • 父节点索引：(i - 1) // 2（向下取整）

例如，对于数组 [9, 7, 6, 3, 2, 5] 构成的最大堆（完全二叉树结构如下）：

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

三、堆的基本操作

堆的核心操作围绕「维持堆的特性」展开，主要包括插入、删除堆顶元素、堆化等，时间复杂度均与树的高度相关（即 O(log n)，n 为元素个数）。

1. 插入元素（以最大堆为例）

步骤：

• 先将新元素插入数组末尾（作为完全二叉树的最后一个节点）。
• 执行「向上调整（Sift Up）」：将新元素与父节点比较，若新元素更大，则交换两者；重复此过程，直到父节点更大或到达根节点（维持最大堆特性）。

示例：向上述最大堆插入 8

• 插入后数组为 [9,7,6,3,2,5,8]，新元素在索引 6，其父节点为索引 2（值为 6）。
• 因 8 > 6，交换后数组为 [9,7,8,3,2,5,6]，此时新元素在索引 2，其父节点为索引 0（值为 9），8 < 9，停止调整。

2. 删除堆顶元素（以最大堆为例）

堆顶元素是最大值（最大堆）或最小值（最小堆），删除步骤：

• 用数组最后一个元素替换堆顶元素（覆盖原堆顶）。
• 删除数组最后一个元素（此时堆的大小减 1）。
• 执行「向下调整（Sift Down）」：从堆顶开始，将当前节点与左右子节点中较大的一个比较，若当前节点更小，则交换；重复此过程，直到当前节点大于子节点或到达叶子节点（维持最大堆特性）。

示例：删除上述堆 [9,7,8,3,2,5,6] 的堆顶 9

• 用最后一个元素 6 替换堆顶，数组变为 [6,7,8,3,2,5]（删除最后一个元素后）。
• 堆顶 6 与左右子节点 7 和 8 中较大的 8 交换，数组变为 [8,7,6,3,2,5]。
• 此时当前节点 6 的子节点为 5（无右子节点），6 > 5，停止调整。

3. 堆化（Heapify）

将一个无序数组转化为堆的过程，时间复杂度为 O(n)（而非 O(n log n)，因底层节点调整次数少）。
步骤：从最后一个非叶子节点（索引 (n//2)-1）开始，依次向前对每个节点执行「向下调整」，直到根节点。

四、堆的类型

• 最大堆：根节点是最大值，适用于需要频繁获取最大值的场景（如最大优先级队列）。
• 最小堆：根节点是最小值，适用于需要频繁获取最小值的场景（如最小优先级队列、Top K 问题）。

五、堆的应用场景

1. 优先队列（Priority Queue）：堆是优先队列的经典实现，能高效获取和删除优先级最高的元素（如操作系统的任务调度，优先级高的任务先执行）。
2. 堆排序：利用堆的特性实现排序，时间复杂度 O(n log n)，步骤为：
   • 将无序数组堆化为最大堆。
   • 反复将堆顶（最大值）与末尾元素交换，缩小堆的范围并重新堆化，最终得到升序数组。
3. Top K 问题：如“从 100 万个数中找最大的 10 个数”，用最小堆（容量为 10）高效解决：遍历所有数，若大于堆顶则替换并堆化，最终堆中元素即为结果（时间复杂度 O(n log K)）。
4. 图算法优化：如 Dijkstra 最短路径算法（用最小堆快速获取当前最短路径节点）、Prim 最小生成树算法（用最小堆获取最小边）。

六、与其他结构的区别

• 与二叉搜索树（BST）：
  • 堆仅要求父节点与子节点的大小关系，左右子节点无明确大小关系（无法通过中序遍历得到有序序列）。
  • BST 要求左子树 < 根 < 右子树，可高效查找任意元素，但获取极值的效率不如堆（堆顶直接是极值，O(1)）。
• 与栈/队列：堆是“优先级驱动”的结构，栈是“后进先出”，队列是“先进先出”，逻辑完全不同。

总结

堆的核心价值是高效维护和获取极值，基于完全二叉树的数组实现使其操作复杂度低至 O(log n)，广泛应用于优先队列、排序、Top K 问题等场景。理解堆的结构特性和调整逻辑（向上/向下调整）是掌握其应用的关键。