Java 优先队列：大顶堆与小顶堆的实现与应用
文章目录
一、什么是优先队列和堆？
1. 优先队列
优先队列是一种特殊的队列，元素出队时不是按照加入顺序，而是根据优先级排序。Java 的 PriorityQueue 是一个无界队列，内部基于堆（Heap）实现。
2. 堆
堆是一种完全二叉树，分为：
- 小顶堆：每个节点的值都小于或等于其子节点的值，根节点是最小值。
- 大顶堆：每个节点的值都大于或等于其子节点的值，根节点是最大值。
PriorityQueue 默认是小顶堆，但可以通过自定义比较器实现大顶堆。
二、Java PriorityQueue 基本用法
1. 默认小顶堆
PriorityQueue 默认按自然顺序（升序）排序，适合需要快速获取最小值的场景。
示例代码
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 添加元素
minHeap.offer(5);
minHeap.offer(2);
minHeap.offer(7);
minHeap.offer(1);
// 输出堆（仅用于调试，实际堆顺序不一定是这样）
System.out.println("堆内容: " + minHeap); // [1, 2, 7, 5]
// 依次移除并输出最小值
while (!minHeap.isEmpty()) {
System.out.print(minHeap.poll() + " "); // 1 2 5 7
}
}
}
输出
堆内容: [1, 2, 7, 5]
1 2 5 7
offer：添加元素。poll：移除并返回堆顶（最小值）。peek：查看堆顶而不移除。
2. 实现大顶堆
Java 默认不支持大顶堆，但可以通过自定义比较器（Comparator）反转顺序，让最大值优先。
示例代码
import java.util.PriorityQueue;
import java.util.Comparator;
public class Main {
public static void main(String[] args) {
// 自定义比较器：降序排序，实现大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
// 添加元素
maxHeap.offer(5);
maxHeap.offer(2);
maxHeap.offer(7);
maxHeap.offer(1);
// 输出堆
System.out.println("堆内容: " + maxHeap); // [7, 2, 5, 1]
// 依次移除并输出最大值
while (!maxHeap.isEmpty()) {
System.out.print(maxHeap.poll() + " "); // 7 5 2 1
}
}
}
输出
堆内容: [7, 2, 5, 1]
7 5 2 1
Comparator.reverseOrder()：内置的降序比较器，直接实现大顶堆。- 也可以手动写比较器：
(a, b) -> b - a。
三、大顶堆与小顶堆的实现细节
1. 内部原理
PriorityQueue 底层是一个数组表示的完全二叉树，通过堆调整算法（Heapify）维护堆性质：
- 小顶堆：插入时从下向上调整（Sift Up），删除时从上向下调整（Sift Down）。
- 大顶堆：通过比较器反转比较规则，逻辑类似。
2. 时间复杂度
- 插入（offer）：O(log n)
- 删除堆顶（poll）：O(log n)
- 查看堆顶（peek）：O(1)
- 空间复杂度：O(n)
四、典型应用场景
1. 小顶堆的应用
- Top K 问题：从大数据中找出最小的 K 个元素。
- 示例：从一亿个数中找最小的 10 个，用小顶堆维护 K 个元素。
- 任务调度：优先处理代价最小的任务。
示例：找最小的 K 个数
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
int[] nums = {4, 5, 1, 6, 2, 7, 3, 8};
int k = 3;
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num);
}
System.out.print("最小的 " + k + " 个数: ");
for (int i = 0; i < k; i++) {
System.out.print(minHeap.poll() + " "); // 1 2 3
}
}
}
2. 大顶堆的应用
- Top K 问题（最大值）：找出最大的 K 个元素。
- 实时排名：维护一个动态的最大值集合。
示例：找最大的 K 个数
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
int[] nums = {4, 5, 1, 6, 2, 7, 3, 8};
int k = 3;
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
for (int num : nums) {
maxHeap.offer(num);
}
System.out.print("最大的 " + k + " 个数: ");
for (int i = 0; i < k; i++) {
System.out.print(maxHeap.poll() + " "); // 8 7 6
}
}
}
五、常见问题与优化
1. 如何处理堆中元素不足的情况？
在 poll 前检查 isEmpty()，避免 NullPointerException。
if (!queue.isEmpty()) {
System.out.println(queue.poll());
} else {
System.out.println("堆为空");
}
2. 如何高效处理 Top K？
对于大数据，维护一个大小为 K 的堆更高效：
- 小顶堆：保留 K 个最大值，超出时移除最小值。
- 大顶堆：保留 K 个最小值，超出时移除最大值。
示例： [优化 Top K]
PriorityQueue<Integer> heap = new PriorityQueue<>(k);
for (int num : nums) {
heap.offer(num);
if (heap.size() > k) {
heap.poll();
}
}
实例真题演练
实现堆排序
问题描述
本题是一道堆排序模板题。
你需要构建一个堆，可以实现如下操作：
push：将一个正整数 xx 插入堆中。remove：删除堆顶元素。若此时堆为空，则输出empty。min：输出堆中最小的元素。若此时堆为空，则输出empty。print：给定一个小于等于当前堆中元素的数字 kk，你需要在一行内输出当前堆中最小的 kk 个元素，并将其全部删除，数据保证该操作不会在堆为空时出现。
输入格式
第一行输入一个整数 nn，表示操作的数量。
接下来 nn 行，每行一个字符串，表示具体的操作。
输出格式
对于 remove，min，print 操作，按照题目要求进行输出。
样例输入
8
push 4
min
remove
remove
push 3
push 7
push 2
print 2
样例输出
4
empty
2 3
import java.util.PriorityQueue;
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<>();//自动实现小顶堆
Scanner scan = new Scanner(System.in);
int num = scan.nextInt();
for(int j =0;j<num;j++){
StringBuilder string = new StringBuilder(scan.next());
if (string.toString().equals("push")) {
int a = scan.nextInt();
queue.add(a);
}
if (string.toString().equals("remove")) {
if (!queue.isEmpty()) {
queue.poll();
} else {
System.out.println("empty");
}
}
if (string.toString().equals("min")) {
if (!queue.isEmpty()) {
System.out.println(queue.peek()) ;
} else {
System.out.println("empty");
}
}
if (string.toString().equals("print")) {
int a = scan.nextInt();
for(int i=0;i<a-1;i++) {
System.out.print(queue.poll()+" ");
}
System.out.println(queue.poll());
}
}
scan.close();
}
}
六、总结
- 小顶堆：默认实现，适合找最小值。
- 大顶堆：通过比较器实现，适合找最大值。
- 应用广泛：Top K、任务调度、实时排序等。
PriorityQueue 是 Java 开发者必备的工具，掌握它的用法能极大提升代码效率。希望这篇博客能帮你在面试或项目中游刃有余！有疑问欢迎留言讨论，喜欢请点赞关注哦！