目录
1、堆（Heap）
1.1、介绍
1.2、大/小堆
1.3、堆的存储方式
1.4、堆实现
1.5、应用场景
2、核心操作
2.1、插入
2.2、删除堆顶
2.3、建堆
前沿
“大堆”和“小堆”是**堆（Heap）**这种数据结构的两种常见形式，广泛应用于优先队列、堆排序、Top-K 问题等场景。
⚠️注意：
- ❌ 堆 ≠ 堆内存（Heap Memory）：这是两个完全不同的概念！
- ❌ 堆不是排序好的数组：只有堆顶有极值保证，其他位置无序。
- ✅ 堆支持动态插入/删除，适合流式数据处理。
Top-K 最大元素（用小堆）
// 找数组中最大的 3 个数 PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 小堆 int[] nums = {1, 5, 3, 9, 2, 8}; int k = 3; for (int num : nums) { minHeap.offer(num); if (minHeap.size() > k) { minHeap.poll(); // 弹出最小的，保留大的 } } // 此时堆中就是最大的 3 个数（无序） System.out.println(minHeap); // 例如 [5, 8, 9]合并 K 个有序链表（小堆），思路是：把每个链表头放入小堆，每次取最小节点。
下面从定义、性质、实现和应用等方面为你详细介绍。
1、堆（Heap）
1.1、介绍
堆是一种特殊的完全二叉树，满足以下两个条件：
1.结构性：
必须是一棵完全二叉树（Complete Binary Tree）→ 所有层都填满，除了最后一层，且最后一层的节点靠左排列。
如下所示：
2.堆序性（Heap Property）：
如下所示：
大堆（Max-Heap）：任意节点的值 ≥ 其子节点的值（根节点是最大值）；
小堆（Min-Heap）：任意节点的值 ≤ 其子节点的值（根节点是最小值）
注意：堆不要求左右子树有序，只要求父子之间满足大小关系。
1.2、大/小堆
特性如下所示：
1.3、堆的存储方式
由于堆是完全二叉树，可以用**数组（顺序存储）**高效表示，无需指针。
假设数组下标从0开始：
- 对于节点 i：
- 父节点：parent = (i - 1) //2
- 左孩子：left = 2*i + 1
- 右孩子：right = 2*i + 2
✅ 优点：节省空间、缓存友好、访问快。
1.4、堆实现
Java 标准库提供了 PriorityQueue 类，它底层就是一个堆：
- 默认是小堆（Min Heap）
- 通过传入 Comparetor 可以实现大堆（Max Heap）
⚠️ 注意：
PriorityQueue 不是线程安全的。如果需要线程安全，可考虑PriorityBlockingQueue。
1、实际应用
小堆示例（数组表示）：
数组: [1, 3, 2, 7, 6, 5, 4] 对应完全二叉树： 1 / \ 3 2 / \ / \ 7 6 5 4→ 每个父节点 ≤ 子节点，根为最小值 1。
代码如下所示：
import java.util.PriorityQueue; public class MinHeapDemo { public static void main(String[] args) { // 默认是最小堆（自然顺序） PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 插入元素 minHeap.offer(10); minHeap.offer(5); minHeap.offer(20); minHeap.offer(1); System.out.println("小堆中的元素（按出队顺序）:"); while (!minHeap.isEmpty()) { System.out.print(minHeap.poll() + " "); // 从小到大输出 } // 输出: 1 5 10 20 } }特点：
- poll() 每次返回最小值
- 适用于找最小值、Top-K 最小等场景
大堆示例：
数组: [9, 7, 8, 2, 6, 5, 4] 树形： 9 / \ 7 8 / \ / \ 2 6 5 4→ 根为最大值 9。Collections.reverseOrder()
Java 的 PriorityQueue 默认是小堆，要实现大堆，需传入逆序比较器：
方法 1：使用 Collections.reverseOrder()
import java.util.PriorityQueue; import java.util.Collections; public class MaxHeapDemo { public static void main(String[] args) { // 使用逆序比较器 → 实现最大堆 PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); maxHeap.offer(10); maxHeap.offer(5); maxHeap.offer(20); maxHeap.offer(1); System.out.println("大堆中的元素（按出队顺序）:"); while (!maxHeap.isEmpty()) { System.out.print(maxHeap.poll() + " "); // 从大到小输出 } // 输出: 20 10 5 1 } }方法 2：使用 Lambda 表达式（更灵活）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); // 或 PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));推荐使用 Integer.compare(b,a) 避免整数溢出问题。
方法3：自定义对象的堆（比如按年龄排序的人）
import java.util.PriorityQueue; class Person { String name; int age; Person(String name, int age) { this.name = name; this.age = age; } @Override public String toString() { return name + "(" + age + ")"; } } public class CustomHeapDemo { public static void main(String[] args) { // 小堆：按年龄从小到大 PriorityQueue<Person> minAgeHeap = new PriorityQueue<>((p1, p2) -> Integer.compare(p1.age, p2.age)); minAgeHeap.offer(new Person("Alice", 30)); minAgeHeap.offer(new Person("Bob", 20)); minAgeHeap.offer(new Person("Charlie", 25)); System.out.println("按年龄从小到大出队:"); while (!minAgeHeap.isEmpty()) { System.out.println(minAgeHeap.poll()); } // 输出: // Bob(20) // Charlie(25) // Alice(30) } }若要大堆（年龄从大到小），只需把比较器改为 (p1,p2) -> Integer.compare(p2.age,p1.age)
Java 的PriorityQueue默认实现的是 小堆（Min Heap），所以poll()返回的是 最小值。
在 PriorityQueue 中：
- poll()：移除并返回堆顶元素
- 堆顶 = 树的根节点
所以关键不是 poll() 本身，而是“堆顶存的是什么？”
小堆 vs 大堆：堆顶不同！
如下所示：
| 堆类型 | 堆顶（根）是什么？ | poll() 返回什么？ |
|---|---|---|
| 小堆（Min Heap） | 最小值 | 最小值 ✅ |
| 大堆（Max Heap） | 最大值 | 最大值 |
结论：
而Java 的PriorityQueue默认是小堆！
这是由它的默认比较器决定的。
为什么 Java 默认用小堆？
因为：
PriorityQueue 的设计初衷是实现优先队列（Priority Queue）
在很多场景中（如任务调度、Dijkstra 算法），我们希望优先处理“最小”的任务（比如最短时间、最低成本）
Java 使用元素的自然顺序（natural ordering），即 Compareable 接口的 compareTo 方法
对于 Integer，自然顺序是从小到大
所以 1<5<100，最小的 1 被放在堆顶
源码逻辑简化如下：
import java.util.PriorityQueue; public class TestPoll { public static void main(String[] args) { PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.offer(10); pq.offer(1); pq.offer(5); System.out.println("堆内部结构（不保证完全有序，但堆顶是最小）:"); System.out.println(pq); // 可能输出 [1, 10, 5] 或类似 System.out.println("第一次 poll(): " + pq.poll()); // 输出 1 System.out.println("第二次 poll(): " + pq.poll()); // 输出 5 System.out.println("第三次 poll(): " + pq.poll()); // 输出 10 } }输出：
堆内部结构（不保证完全有序，但堆顶是最小）: [1, 10, 5] 第一次 poll(): 1 第二次 poll(): 5 第三次 poll(): 10👉 可见，堆顶始终是最小值，所以poll()先返回 1。
把 PriorityQueue 想象成一个自动排序的队列，但它只保证“最重要的元素在最前面”：所以堆的方向取决于你的“优先级定义”。
1.5、应用场景
如下所示：
2、核心操作
2.1、插入
- 将新元素放到数组末尾；
- 然后“上浮”（sift-up / bubble-up）：与父节点比较，若违反堆序性则交换，直到满足为止。
时间复杂度：O(log n)
2.2、删除堆顶
- 将堆顶（根）与最后一个元素交换；
- 删除最后一个元素（原堆顶）；
- 对新根进行“下沉”（sift-down / heapify-down）：与较小（小堆）或较大（大堆）的子节点交换，直到满足堆序性。
时间复杂度：O(log n)
2.3、建堆
- 给定一个无序数组，可在O(n)时间内构建堆（从最后一个非叶子节点开始向下调整）。
参考文章：
1、堆排序详细图解
