堆（Heap）与优先队列

描述
堆是一种特殊的完全二叉树，满足以下性质：

• 最小堆：每个节点的值都小于或等于其子节点的值（根节点最小）。
• 最大堆：每个节点的值都大于或等于其子节点的值（根节点最大）。
  堆常用于实现优先队列（一种支持按优先级动态获取最高/最低值元素的数据结构），典型应用包括任务调度、Dijkstra算法等。

1. 堆的存储结构

堆通常用数组存储，利用完全二叉树的特性：

• 根节点索引为 0（或 1，这里以 0 为例）。
• 对于节点 i：
  • 父节点索引：(i-1)//2
  • 左子节点索引：2*i+1
  • 右子节点索引：2*i+2

示例（最小堆）：

数组：[1, 3, 6, 5, 9, 8]  
对应树结构：
      1
    /   \
   3     6
  / \   /
 5   9 8

2. 堆的核心操作

（1）插入元素（上浮操作）

步骤：

1. 将新元素添加到数组末尾（完全二叉树的最后一个位置）。
2. 上浮（Sift Up）：
   • 比较新节点与其父节点的值。
   • 若新节点值小于父节点（最小堆），则交换两者。
   • 重复直到根节点或满足堆性质。

示例：向上述堆插入 2

初始堆：[1, 3, 6, 5, 9, 8]  
插入 2 → [1, 3, 6, 5, 9, 8, 2]  
上浮过程：
  2 的父节点是 6（索引 2），2<6 → 交换 → [1, 3, 2, 5, 9, 8, 6]  
  2 的父节点是 3（索引 1），2<3 → 交换 → [1, 2, 3, 5, 9, 8, 6]  
  2 的父节点是 1（索引 0），2>1 → 停止。  
最终堆：[1, 2, 3, 5, 9, 8, 6]

（2）删除堆顶元素（下沉操作）

步骤：

1. 用数组末尾元素替换堆顶元素，并删除末尾。
2. 下沉（Sift Down）：
   • 从根节点开始，比较其与左右子节点的值。
   • 选择值最小的子节点（最小堆）交换。
   • 重复直到叶子节点或满足堆性质。

示例：删除堆顶元素 1

初始堆：[1, 2, 3, 5, 9, 8, 6]  
用末尾元素 6 替换堆顶 → [6, 2, 3, 5, 9, 8]  
下沉过程：
  6 的子节点为 2 和 3，最小子节点是 2，6>2 → 交换 → [2, 6, 3, 5, 9, 8]  
  6 的子节点为 5 和 9，最小子节点是 5，6>5 → 交换 → [2, 5, 3, 6, 9, 8]  
  6 无子节点 → 停止。  
最终堆：[2, 5, 3, 6, 9, 8]

3. 堆的构建（Heapify）

将无序数组快速构建为堆：

• 从最后一个非叶子节点开始（索引 n//2-1），向前依次对每个节点执行下沉操作。
• 时间复杂度：O(n)（非 O(n log n)）。

示例：将 [5, 3, 8, 1, 9] 构建为最小堆

步骤：
  非叶子节点索引：5//2-1=1 → 从索引 1（值 3）开始：
    - 索引 1：3 的子节点为 1 和 9，最小子节点 1<3 → 交换 → [5, 1, 8, 3, 9]  
  下一个索引 0（值 5）：
    - 5 的子节点为 1 和 8，最小子节点 1<5 → 交换 → [1, 5, 8, 3, 9]  
    - 5 的子节点为 3 和 9，最小子节点 3<5 → 交换 → [1, 3, 8, 5, 9]  
最终堆：[1, 3, 8, 5, 9]

4. 优先队列的实现

基于堆的优先队列支持以下操作：

• push(x)：插入元素（上浮） → O(log n)
• pop()：删除堆顶（下沉） → O(log n)
• peek()：返回堆顶值 → O(1)

应用场景：

• 任务调度（按优先级执行）
• 合并 K 个有序链表（每次取最小节点）
• 求数据流的中位数（双堆技巧）

5. 总结

• 堆通过上浮/下沉维护有序性，保证高效动态操作。
• 优先队列是堆的典型应用，适合需要频繁获取最值的场景。
• 注意堆的构建时间复杂度为 O(n)，优于逐个插入的 O(n log n)。