东莞广告设计公司排名_上海网站公司排名_seo免费资源大全_制作网页的网站

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();}
}

---

实例真题演练

实现堆排序

问题描述

本题是一道堆排序模板题。

你需要构建一个堆，可以实现如下操作：

1. push：将一个正整数 xx 插入堆中。
2. remove：删除堆顶元素。若此时堆为空，则输出 empty。
3. min：输出堆中最小的元素。若此时堆为空，则输出 empty。
4. 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 开发者必备的工具，掌握它的用法能极大提升代码效率。希望这篇博客能帮你在面试或项目中游刃有余！有疑问欢迎留言讨论，喜欢请点赞关注哦！

---