【java中优先队列】在Java编程语言中，优先队列（Priority Queue）是一种非常实用的数据结构，它允许我们按照特定的顺序（如元素的自然顺序或自定义比较器）来存储和取出元素。与普通的队列不同，优先队列不是遵循“先进先出”（FIFO）的原则，而是根据元素的优先级来决定出队的顺序。
一、优先队列的基本概念
| 概念 | 说明 |
| 优先队列 | 一种特殊的队列，元素按优先级排序，每次取出的是当前优先级最高的元素 |
| 元素排序 | 可以是自然顺序（如数字大小）或通过Comparator自定义排序 |
| 底层实现 | 基于堆结构（通常为二叉堆）实现 |
| 特点 | 插入和删除操作的时间复杂度为O(log n) |
二、Java中的优先队列类
Java中提供了一个名为`PriorityQueue`的类，位于`java.util`包下。它实现了`Queue`接口，并支持泛型。
示例代码：
```java
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
PriorityQueue
pq.add(5);
pq.add(2);
pq.add(9);
pq.add(1);
System.out.println("Priority Queue: " + pq);
System.out.println("Polling elements:");
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
}
}
```
输出结果：
```
Priority Queue: [1, 2, 9, 5
Polling elements:
1 2 5 9
```
三、优先队列的常用方法
| 方法 | 说明 |
| `add(E e)` | 将元素插入队列 |
| `offer(E e)` | 与`add()`类似，但返回布尔值表示是否成功 |
| `poll()` | 移除并返回队列头部元素（即最小元素） |
| `peek()` | 返回队列头部元素，不移除 |
| `remove(Object o)` | 移除指定元素 |
| `contains(Object o)` | 判断队列是否包含指定元素 |
四、自定义排序方式
如果需要按照非自然顺序（如降序）排序，可以使用`Comparator`接口进行自定义排序。
示例代码：
```java
import java.util.Comparator;
import java.util.PriorityQueue;
public class CustomPriorityQueueExample {
public static void main(String[] args) {
PriorityQueue
pq.add(5);
pq.add(2);
pq.add(9);
pq.add(1);
System.out.println("Custom Priority Queue (Descending): " + pq);
System.out.println("Polling elements:");
while (!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
}
}
```
输出结果：
```
Custom Priority Queue (Descending): [9, 5, 2, 1
Polling elements:
9 5 2 1
```
五、注意事项
| 注意事项 | 说明 |
| 不保证线程安全 | 多线程环境下应使用`PriorityBlockingQueue` |
| 不允许null元素 | 如果插入null会抛出NullPointerException |
| 无界队列 | 默认没有容量限制，但可设置初始容量 |
| 适合场景 | 图算法（如Dijkstra）、任务调度等 |
六、总结
Java中的`PriorityQueue`是一个高效且灵活的集合类，适用于需要按优先级处理元素的场景。通过自定义比较器，可以轻松实现不同的排序逻辑。了解其基本用法和注意事项，有助于在实际项目中更好地应用这一数据结构。