Java[优先队列---原理及使用]·简_java优先队列

技术文档

在使用优先队列之前，我们需要先明白为什么要使用优先队列、使用优先队列的好处、优先队列的局限性等内容。本文围绕优先队列的原理以及使用场景进行介绍，并提供部分代码用例以供参考。

一、优先队列和普通队列的区别

1.核心区别概览

特性 普通队列（FIFO） 优先队列（Priority Queue） 出队顺序 先进先出（FIFO）优先级高的元素先出队 排序规则 按元素入队顺序按元素优先级（自然顺序或自定义比较器） 底层实现 链表、数组（循环队列）堆（二叉堆、斐波那契堆等） 插入 / 删除复杂度 O(1) O(log n) 获取队首元素 O(1) O(1) 应用场景 任务调度（按顺序处理）优先级调度（如操作系统线程调度）

普通队列按照元素入队的顺序先进先出，优先队列出队则是按元素优先级，将高优先级的元素先进行出队操作。

普通队列（FIFO）

特点：元素按照入队顺序出队，先进入的元素先被处理。

示例：

Queue queue = new LinkedList();queue.offer(3); // 入队顺序: 3 → 1 → 2queue.offer(1);queue.offer(2);System.out.println(queue.poll()); // 输出: 3（先入先出）

优先队列（Priority Queue）

特点：元素按优先级排序，优先级高的元素先出队。

示例（小顶堆）：

PriorityQueue pq = new PriorityQueue();pq.offer(3); // 入队元素: 3, 1, 2pq.offer(1);pq.offer(2);System.out.println(pq.poll()); // 输出: 1（最小值优先）

2. 底层实现差异

数据结构 普通队列 优先队列 存储方式 链表或数组（循环队列）堆（二叉堆，通常用数组实现） 元素关系 无特殊关系，仅维护头尾指针完全二叉树，父节点 ≤ 子节点（小顶堆） 插入操作 直接添加到队尾（O (1)）插入后需调整堆结构（O (log n)） 删除操作 直接移除队首（O (1)）删除堆顶后需调整堆结构（O (log n)）

3. 复杂度对比

操作 普通队列 优先队列 插入（enqueue） O(1) O(log n) 删除（dequeue） O(1) O(log n) 查看队首 O(1) O(1) 查找特定元素 O(n) O(n) 遍历（无序） O(n) O(n) 遍历（有序） O(n log n) O(n log n)

5. 应用场景对比

普通队列适用场景

任务按顺序处理（如消息队列、打印任务队列）。
BFS（广度优先搜索）算法。
资源池（如数据库连接池）。

优先队列适用场景

优先级调度（如操作系统线程调度、医院急诊排序）。
贪心算法（如 Dijkstra 最短路径算法）。
动态维护 Top-K 元素（如实时热搜榜）。
合并多个有序序列（如归并排序的优化）。

选择使用普通队列还是优先队列，取决于具体需求：

若需严格按顺序处理元素，使用普通队列。
若需根据优先级动态调整处理顺序，使用优先队列。

优先队列通过牺牲插入 / 删除的常数时间复杂度（O (1) → O (log n)），换取了动态维护元素优先级的能力，适用于需要频繁获取极值的场景

二、优先队列的使用

排序方式：
- 自然顺序：元素必须实现Comparable接口。
- 自定义顺序：通过构造函数传入Comparator。

1. 常用方法

方法描述 add(E e) 添加元素，失败时抛出异常（如容量限制）。 offer(E e) 添加元素，失败时返回false。 remove() 移除队首元素，队列为空时抛出异常。 poll() 移除队首元素，队列为空时返回null。 element() 获取队首元素，队列为空时抛出异常。 peek() 获取队首元素，队列为空时返回null。 size() 返回队列中的元素个数。 contains(Object o) 判断队列中是否包含指定元素。 clear() 清空队列。

2. 自然顺序示例（元素实现`Comparable`）

import java.util.PriorityQueue;public class PriorityQueueExample { public static void main(String[] args) { // 创建优先队列（默认自然顺序，小顶堆） PriorityQueue pq = new PriorityQueue(); // 添加元素 pq.offer(30); pq.offer(10); pq.offer(20); // 遍历（不保证顺序） System.out.println(\"遍历队列: \" + pq); // 输出可能是 [10, 30, 20] // 按优先级出队 while (!pq.isEmpty()) { System.out.print(pq.poll() + \" \"); // 输出: 10 20 30 } }}

3. 自定义顺序示例（通过`Comparator`）

import java.util.PriorityQueue;import java.util.Comparator;public class CustomPriorityQueue { public static void main(String[] args) { // 创建优先队列（自定义降序排序，大顶堆） PriorityQueue pq = new PriorityQueue(Comparator.reverseOrder()); pq.offer(3); pq.offer(1); pq.offer(2); // 按优先级出队 while (!pq.isEmpty()) { System.out.print(pq.poll() + \" \"); // 输出: 3 2 1 } }}

4. 自定义对象示例

import java.util.PriorityQueue;import java.util.Comparator;class Student implements Comparable { private String name; private int score; public Student(String name, int score) { this.name = name; this.score = score; } // 按分数降序排序 @Override public int compareTo(Student other) { return other.score - this.score; } @Override public String toString() { return name + \"(\" + score + \")\"; }}public class CustomObjectExample { public static void main(String[] args) { PriorityQueue pq = new PriorityQueue(); pq.offer(new Student(\"Alice\", 85)); pq.offer(new Student(\"Bob\", 92)); pq.offer(new Student(\"Charlie\", 78)); // 按分数从高到低出队 while (!pq.isEmpty()) { System.out.print(pq.poll() + \" \"); // 输出: Bob(92) Alice(85) Charlie(78) } }}

5. 注意事项

线程安全：PriorityQueue是非线程安全的。若需线程安全，使用PriorityBlockingQueue。

import java.util.concurrent.PriorityBlockingQueue;PriorityBlockingQueue threadSafePQ = new PriorityBlockingQueue();

空值处理：不允许插入null元素，否则会抛出NullPointerException。
复杂度：
- 插入 / 删除：O (log n)
- 获取队首：O (1)
遍历顺序：iterator()返回的迭代器不保证有序，若需有序遍历，可先转为数组再排序。
```
Object[] sortedArray = pq.toArray();Arrays.sort(sortedArray);
```

三、优先队列的存储结构

优先队列（PriorityQueue）的底层实现是二叉堆（Binary Heap），它在堆内存中的存储结构可以从逻辑和物理两个层面来理解：

1. 逻辑结构：完全二叉树

二叉堆是一种完全二叉树，每个节点的值满足：
- 小顶堆：每个节点的值 ≤ 其子节点的值，根节点是最小值。
- 大顶堆：每个节点的值 ≥ 其子节点的值，根节点是最大值。
完全二叉树的特点：
- 除最后一层外，每一层都被完全填充。
- 最后一层的节点从左到右依次排列。

示例（小顶堆）：

 10 / \\ 20 30 / \\ 40 50

2. 物理存储：动态数组

虽然逻辑上是树结构，但 Java 的PriorityQueue在堆内存中实际使用动态数组存储元素。数组索引与树节点的映射关系为：

根节点：数组索引0。
节点i的左子节点：索引2i + 1。
节点i的右子节点：索引2i + 2。
节点i的父节点：索引(i-1)/2（向下取整）。

示例数组存储：

[10, 20, 30, 40, 50]

对应的树结构：

索引0: 10 / \\索引1: 20 索引2: 30 / \\索引3:40 索引4:50

3. 堆内存中的存储细节

数组扩容

PriorityQueue使用动态数组，默认初始容量为11。
当元素数量超过容量时，数组会自动扩容：
- 若容量 < 64，翻倍扩容（+2）。
- 若容量 ≥ 64，扩容 50%。

对象引用

若存储自定义对象，数组中保存的是对象的引用，而非对象本身。
对象实际数据存储在堆的其他区域，数组仅保存指向这些对象的指针。

示例：

PriorityQueue pq = new PriorityQueue();pq.offer(new Student(\"Alice\", 90));

堆内存布局：

数组[0] → Student对象（name=\"Alice\", score=90）

4. 堆操作的实现

插入元素（`offer()`）

将元素添加到数组末尾（树的最后一个位置）。
向上调整（siftUp）：若新元素比父节点小，则交换，直到满足堆性质。

示例（插入 5）：

插入前：[10, 20, 30, 40, 50]插入后：[5, 10, 30, 40, 50, 20]

调整过程：

1. 初始插入：5放在索引5（最后位置）2. 比较5与父节点20（索引2），交换 → [5, 10, 30, 40, 50, 20]3. 比较5与父节点10（索引0），交换 → [5, 10, 30, 40, 50, 20]最终结构： 5 / \\ 10 30 / \\ / 40 50 20

删除元素（`poll()`）

移除根节点（数组首元素）。
将数组最后一个元素移到根节点位置。
向下调整（siftDown）：若新根节点比子节点大，则与较小的子节点交换，直到满足堆性质。

5. 与其他数据结构的对比

数据结构插入时间复杂度删除最小值时间复杂度空间复杂度优先队列（堆） O(log n) O(log n) O(n) 有序数组 O(n) O(1) O(n) 无序数组 O(1) O(n) O(n)

Java 优先队列在堆内存中的核心特点：

逻辑结构：完全二叉树（小顶堆 / 大顶堆）。
物理存储：动态数组，通过索引映射实现树的父子关系。
操作效率：插入和删除操作通过堆化（heapify）维持 O (log n) 时间复杂度。
对象存储：数组保存对象引用，实际对象数据在堆的其他区域。

四、优先队列的线程安全问题

1. 非线程安全的`PriorityQueue`

类定义：java.util.PriorityQueue
线程安全特性：非线程安全
问题场景：多线程环境下，若多个线程同时修改队列（如插入、删除），可能导致：
- 数据不一致：例如两个线程同时插入元素，可能破坏堆结构。
- 抛出异常：如ConcurrentModificationException。

示例（多线程问题）：

import java.util.PriorityQueue;public class PriorityQueueThreadUnsafe { private static PriorityQueue pq = new PriorityQueue(); public static void main(String[] args) throws InterruptedException { // 线程1：插入元素 Thread t1 = new Thread(() -> { for (int i = 0; i  { for (int i = 0; i < 500; i++) { pq.poll(); } }); t1.start(); t2.start(); t1.join(); t2.join(); System.out.println(\"队列大小: \" + pq.size()); // 可能输出非预期结果 }}

2. 线程安全的`PriorityBlockingQueue`

类定义：java.util.concurrent.PriorityBlockingQueue
线程安全特性：完全线程安全
实现原理：
- 内部锁机制：使用ReentrantLock保证原子性。
- 动态扩容：插入元素时若队列满，会自动扩容，避免阻塞。
关键方法：与PriorityQueue类似，但所有操作都是线程安全的。

示例（线程安全使用）：

import java.util.concurrent.PriorityBlockingQueue;public class PriorityBlockingQueueExample { private static PriorityBlockingQueue queue = new PriorityBlockingQueue(); public static void main(String[] args) throws InterruptedException { // 生产者线程 Thread producer = new Thread(() -> { for (int i = 0; i  { for (int i = 0; i < 500; i++) { try {  Integer num = queue.take(); // 阻塞直到有元素  System.out.println(\"消费: \" + num); } catch (InterruptedException e) {  Thread.currentThread().interrupt(); } } }); producer.start(); consumer.start(); producer.join(); consumer.join(); System.out.println(\"队列大小: \" + queue.size()); // 正确输出500 }}

3. 线程安全机制对比

特性 PriorityQueue PriorityBlockingQueue 线程安全性 非线程安全线程安全 锁机制 无 ReentrantLock 阻塞操作 无支持take()、put()阻塞方法 扩容策略 手动触发自动扩容（线程安全） 性能（单线程） 高（无锁开销）低（有锁开销） 性能（多线程） 不可用（需手动同步）高（锁优化）

4. 同步包装器`Collections.synchronizedQueue()`

使用方式：

PriorityQueue pq = new PriorityQueue();Queue syncQueue = Collections.synchronizedQueue(pq);

局限性：
- 仅外部同步：仅对队列整体加锁，无法保证复合操作（如poll()后立即offer()）的原子性。
- 性能较差：锁粒度大，所有操作串行化。
适用场景：简单场景，对性能要求不高。

5. 并发场景下的选择建议

场景 推荐实现 原因单线程环境 PriorityQueue 无锁开销，性能最优多线程读多写少 PriorityBlockingQueue 锁粒度细，支持并发读写多线程写多读少且需阻塞语义 PriorityBlockingQueue 支持take()/put()阻塞方法，避免轮询需兼容旧代码且对性能要求不高 Collections.synchronizedQueue() 简单易用，但锁粒度大

6. 注意事项

自定义对象的线程安全：若队列存储自定义对象，需确保对象自身是线程安全的（如不可变对象）。
迭代器的弱一致性：PriorityBlockingQueue的迭代器是弱一致性的，可能反映迭代器创建时的状态，不抛出ConcurrentModificationException。
公平性：PriorityBlockingQueue默认非公平锁，若需公平性，可通过构造函数指定

五、优先队列的具体应用场景

1. 任务调度系统

场景描述：根据任务优先级动态调整执行顺序，高优先级任务优先处理。

实现：

PriorityQueue taskQueue = new PriorityQueue( Comparator.comparingInt(Task::getPriority).reversed());// 高优先级任务先执行taskQueue.offer(new Task(\"紧急任务\", 1));taskQueue.offer(new Task(\"普通任务\", 3));taskQueue.offer(new Task(\"重要任务\", 2));while (!taskQueue.isEmpty()) { System.out.println(\"处理: \" + taskQueue.poll().getName());}

2. 定时任务（延迟队列）

场景描述：任务按执行时间排序，时间最早的任务优先执行。

实现：

import java.util.concurrent.DelayQueue;import java.util.concurrent.Delayed;import java.util.concurrent.TimeUnit;class DelayedTask implements Delayed { private final long executeTime; public DelayedTask(long delayMillis) { this.executeTime = System.currentTimeMillis() + delayMillis; } @Override public long getDelay(TimeUnit unit) { return unit.convert(executeTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS); } @Override public int compareTo(Delayed other) { return Long.compare(this.executeTime, ((DelayedTask) other).executeTime); }}// 使用DelayQueue（基于PriorityQueue实现）DelayQueue queue = new DelayQueue();queue.put(new DelayedTask(5000)); // 5秒后执行

Java[优先队列---原理及使用]·简_java优先队列

一、优先队列和普通队列的区别

1.核心区别概览

普通队列（FIFO）

优先队列（Priority Queue）

2. 底层实现差异

3. 复杂度对比

5. 应用场景对比

普通队列适用场景

优先队列适用场景

二、优先队列的使用

1. 常用方法

2. 自然顺序示例（元素实现`Comparable`）

3. 自定义顺序示例（通过`Comparator`）

4. 自定义对象示例

5. 注意事项

三、优先队列的存储结构

1. 逻辑结构：完全二叉树

2. 物理存储：动态数组

3. 堆内存中的存储细节

数组扩容

对象引用

4. 堆操作的实现

插入元素（`offer()`）

删除元素（`poll()`）

5. 与其他数据结构的对比

四、优先队列的线程安全问题

1. 非线程安全的`PriorityQueue`

2. 线程安全的`PriorityBlockingQueue`

3. 线程安全机制对比

4. 同步包装器`Collections.synchronizedQueue()`

5. 并发场景下的选择建议

6. 注意事项

五、优先队列的具体应用场景

1. 任务调度系统

2. 定时任务（延迟队列）

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

Java[优先队列---原理及使用]·简_java优先队列

一、优先队列和普通队列的区别

1.核心区别概览

普通队列（FIFO）

优先队列（Priority Queue）

2. 底层实现差异

3. 复杂度对比

5. 应用场景对比

普通队列适用场景

优先队列适用场景

二、优先队列的使用

1. 常用方法

2. 自然顺序示例（元素实现Comparable）

3. 自定义顺序示例（通过Comparator）

4. 自定义对象示例

5. 注意事项

三、优先队列的存储结构

1. 逻辑结构：完全二叉树

2. 物理存储：动态数组

3. 堆内存中的存储细节

数组扩容

对象引用

4. 堆操作的实现

插入元素（offer()）

删除元素（poll()）

5. 与其他数据结构的对比

四、优先队列的线程安全问题

1. 非线程安全的PriorityQueue

2. 线程安全的PriorityBlockingQueue

3. 线程安全机制对比

4. 同步包装器Collections.synchronizedQueue()

5. 并发场景下的选择建议

6. 注意事项

五、优先队列的具体应用场景

1. 任务调度系统

2. 定时任务（延迟队列）

相关问题

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

2. 自然顺序示例（元素实现`Comparable`）

3. 自定义顺序示例（通过`Comparator`）

插入元素（`offer()`）

删除元素（`poll()`）

1. 非线程安全的`PriorityQueue`

2. 线程安全的`PriorityBlockingQueue`

4. 同步包装器`Collections.synchronizedQueue()`