堆(优先队列) heap 入门介绍

1️⃣ 堆的概念

堆是一种 完全二叉树（Complete Binary Tree） 的数据结构，同时满足 堆性质（Heap Property）：

• 最大堆（Max-Heap）：每个节点的值都 大于等于其子节点的值。
• 最小堆（Min-Heap）：每个节点的值都 小于等于其子节点的值。

特点：

1. 完全二叉树：树除了最后一层外，其他层都满；最后一层从左到右依次填充。
2. 根节点是堆中最大（最大堆）或最小（最小堆）的值。
3. 堆一般用 数组 来实现，而不是指针型节点。

---

2️⃣ 堆的表示（数组实现）

因为堆是完全二叉树，所以可以用数组表示，节点索引从 0 开始：

• 对于索引为 i 的节点：

  • 左子节点索引：2*i + 1
  • 右子节点索引：2*i + 2
  • 父节点索引：(i - 1) / 2（向下取整）

例子：最大堆

数组：[90, 15, 10, 7, 12, 2]
对应完全二叉树：

        90
       /  \
     15    10
    / \   /
   7  12 2

可以看到，根节点 90 最大，每个父节点都大于等于子节点。

---

3️⃣ 堆的核心操作

（1）插入元素 insert

• 步骤：

  1. 将新元素放在数组末尾（保持完全二叉树性质）。

  2. “上浮”（bubble-up / sift-up）：

     • 如果新元素比父节点大（最大堆），就交换。
     • 直到堆性质满足或到达根节点。

• 时间复杂度：O(log n)（树高为 log n）

---

（2）删除堆顶 extract / pop

• 步骤：

  1. 移除根节点（最大堆最大元素）。

  2. 用最后一个元素填补根节点。

  3. “下沉”（bubble-down / sift-down）：

     • 与左右子节点比较，选最大的交换。
     • 直到堆性质满足或到达叶子节点。

• 时间复杂度：O(log n)

---

（3）堆化（Heapify）

• 将任意数组变成堆。

• 自下而上方式：

  • 从最后一个非叶子节点开始，执行下沉操作。

• 时间复杂度：O(n)，比重复插入效率高。

---

（4）获取堆顶

• 直接访问数组第 0 个元素。
• 时间复杂度：O(1)

---

4️⃣ 堆的类型

类型	堆性质	根节点
最大堆	父节点 ≥ 子节点	最大值
最小堆	父节点 ≤ 子节点	最小值

在应用上：

• 最大堆 → 优先获取最大值
• 最小堆 → 优先获取最小值

---

5️⃣ 堆的应用场景

1. 优先队列（Priority Queue）

   • 堆是实现优先队列的经典方式。
   • 插入元素和获取最大/最小元素都很高效。
   • 例：任务调度、操作系统 CPU 调度

2. 堆排序（Heap Sort）

   • 利用最大堆从大到小排序。
   • 时间复杂度：O(n log n)，空间复杂度：O(1)（数组原地排序）

3. Top-K 问题

   • 找前 K 大/小元素
   • 用大小为 K 的最小堆或最大堆维护

4. 合并 K 个有序数组

   • 使用最小堆维护当前最小元素

5. 图算法

   • Dijkstra 最短路径
   • Prim 最小生成树

---

6️⃣ 堆的代码示例（Java）

import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) {
        // 最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(5);
        minHeap.add(3);
        minHeap.add(7);
        System.out.println(minHeap.peek()); // 3

        minHeap.poll(); // 删除堆顶
        System.out.println(minHeap.peek()); // 5

        // 最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        maxHeap.add(5);
        maxHeap.add(3);
        maxHeap.add(7);
        System.out.println(maxHeap.peek()); // 7
    }
}

---

7️⃣ 小结

• 堆是一种 完全二叉树，满足堆性质。

• 可以用 数组 高效实现。

• 核心操作：

  • 插入：O(log n) 上浮
  • 删除堆顶：O(log n) 下沉
  • 堆化整个数组：O(n)

• 常用类型：

  • 最大堆 → 获取最大值
  • 最小堆 → 获取最小值

• 广泛应用于：

  • 优先队列
  • 堆排序
  • Top-K 问题
  • 图算法