Java 优先级队列（PriorityQueue）

一、什么是优先级队列1. 核心定义优先级队列是一种有序队列区别于普通队列 “先进先出FIFO” 的规则它的出队顺序由元素的优先级决定每次调用poll()出队或peek()查看队首时返回的是队列中优先级最高或最低的元素元素的优先级可通过自然排序实现Comparable接口或自定义比较器Comparator指定Java 中PriorityQueue是无界队列默认初始容量 11可自动扩容线程不安全并发场景下需用PriorityBlockingQueue阻塞优先级队列。2. 与普通队列的区别特性普通队列LinkedList/ArrayDeque优先级队列PriorityQueue排序规则先进先出FIFO/ 后进先出LIFO按元素优先级排序自然序 / 自定义出队元素队首元素最早入队优先级最高 / 最低元素底层实现链表 / 数组二叉堆默认小顶堆线程安全不安全需手动同步不安全并发用 PriorityBlockingQueue容量特性可无界 / 有界默认无界可指定初始容量3. 核心应用场景任务调度按任务优先级执行如线程池中的延迟任务、优先级任务topK 问题快速获取前 K 个最大 / 最小元素如 Top10 热门商品、前 5 高分评论最短路径算法Dijkstra 算法中用优先级队列选择当前最短路径节点事件驱动按事件紧急程度处理如系统告警、消息推送。二、优先级队列的底层原理二叉堆Java 的PriorityQueue底层基于二叉堆Binary Heap实现这是一种完全二叉树结构分为 “小顶堆” 和 “大顶堆”小顶堆每个父节点的值 ≤ 其子节点的值队首堆顶是最小值Java 默认大顶堆每个父节点的值 ≥ 其子节点的值队首堆顶是最大值。1. 完全二叉树与数组存储二叉堆是完全二叉树除最后一层外每一层节点数都满最后一层从左到右连续因此可以用数组高效存储若父节点索引为i则左子节点索引 2*i 1右子节点索引 2*i 2若子节点索引为j则父节点索引 (j - 1) / 2整数除法。例小顶堆的数组存储结构元素[1,3,2,5,4]数组索引0 1 2 3 4 元素值 1 3 2 5 4 对应的完全二叉树 10 / \ 3122 / \ 53442. 堆的核心操作维护堆特性优先级队列的入队offer()和出队poll()操作本质是堆的 “上浮siftUp” 和 “下沉siftDown”目的是维护堆的有序性。1入队siftUp上浮当新元素入队时插入到数组末尾完全二叉树的最后一个节点然后通过 “上浮” 调整位置直到满足堆特性新元素索引j 数组长度 - 1计算父节点索引i (j-1)/2比较新元素与父节点若新元素优先级更高小顶堆中值更小则交换两者重复步骤 2-3直到父节点优先级更高或到达堆顶j0。例向上述小顶堆中插入元素0插入后数组[1,3,2,5,4,0] → 新元素索引5父节点索引2元素20 → 数组[1,3,0,5,4,2] → 新元素索引2父节点索引0元素10 交换 → 数组[0,3,2,5,4,1] → 到达堆顶上浮结束。2出队siftDown下沉当堆顶元素出队时用数组末尾元素替换堆顶然后通过 “下沉” 调整位置直到满足堆特性堆顶元素索引0出队将末尾元素索引size-1移到堆顶数组长度减 1当前节点索引i0计算左右子节点索引left1、right2找到左右子节点中优先级最高的节点小顶堆中值最小记为minChildIndex比较当前节点与minChildIndex对应的元素若当前节点优先级更低则交换两者重复步骤 2-4直到当前节点优先级更高或无子节点left size。例从上述小顶堆 [0,3,2,5,4,1] 中出队取出0末尾元素1移到堆顶 → 数组[1,3,2,5,4]size5当前节点1索引0左右子节点3索引1、2索引2 → 最小子节点是2索引21 2 → 无需交换下沉结束堆仍满足小顶堆特性。三、Java PriorityQueue 核心 API 与使用1. 构造方法4 种常用PriorityQueue提供多个构造方法核心是指定 “初始容量” 和 “排序规则”// 1. 默认构造初始容量11自然排序元素需实现Comparable PriorityQueueInteger pq1 new PriorityQueue// 2. 指定初始容量容量可自动扩容自然排序 PriorityQueueInteger pq2 new PriorityQueue); // 3. 自定义比较器指定优先级规则如大顶堆 PriorityQueue maxHeap new PriorityQueue) - b - a); // 4. 从集合初始化将集合元素转为优先级队列 ListInteger list Arrays.asList(3,1,2); PriorityQueue pq4 new PriorityQueue ⚠️ 注意 - 若使用自然排序元素必须实现Comparable接口如Integer、String否则会抛出ClassCastException - 初始容量只是“初始大小”队列满时会自动扩容扩容规则当容量64时翻倍≥64时扩容50%。 ### 2. 核心方法常用操作 | 方法名 | 功能描述 | 注意点 | |----------------|-------------------------------------------|-----------------------------------------| | offer(E e) | 入队添加元素返回true无界队列永不失败 | 触发siftUp操作 | | poll() | 出队取出并删除堆顶元素队列为空返回null | 触发siftDown操作 | | peek() | 查看堆顶元素队列为空返回null | 不修改队列仅查询 | | size() | 返回队列中元素个数 | - | | isEmpty() | 判断队列是否为空 | - | | clear() | 清空队列 | - | | contains(Object o) | 判断是否包含指定元素 | 遍历整个数组时间复杂度O(n) | | toArray() | 转为数组返回 | 数组元素无序仅存储结构未排序 | ### 3. 关键使用示例 #### 1自然排序小顶堆 java public class PriorityQueueDemo { public static void main(String[] args) { PriorityQueue new PriorityQueue // 入队 minHeap.offer(5); minHeap.offer(2); minHeap.offer(8); minHeap.offer(1); // 出队按优先级1→2→5→8 while (!minHeap.isEmpty()) { System.out.print(minHeap.poll() ); // 输出1 2 5 8 } } }2自定义比较器大顶堆通过Comparator接口指定 “大的元素优先级高”public class MaxHeapDemo { public static void main(String[] args) { // 自定义比较器b - a 表示“a 优先级更高” PriorityQueue new PriorityQueue, b) - b - a); maxHeap.offer(5); maxHeap.offer(2); maxHeap.offer(8); maxHeap.offer(1); while (!maxHeap.isEmpty()) { System.out.print(maxHeap.poll() ); // 输出8 5 2 1 } } }3存储自定义对象需实现 Comparable自定义User类按age升序排序自然排序class User implements Comparable { private String name; private int age; public User(String name, int age) { this.name name; this.age age; } // 自然排序按age升序age越小优先级越高 Override public int compareTo(User o) { return this.age - o.age; } Override public String toString() { return User{name name , age age }; } } public class CustomObjectDemo { public static void main(String[] args) { PriorityQueueq new PriorityQueue(); pq.offer(new User(张三, 25)); pq.offer(new User(李四, 20)); pq.offer(new User(王五, 30)); while (!pq.isEmpty()) { System.out.println(pq.poll()); // 输出 // User{name李四, age20} // User{name张三, age25} // User{name王五, age30} } } }四、PriorityQueue 源码核心逻辑解析JDK81. 核心成员变量public class PriorityQueueE extends AbstractQueue { private transient Object[] queue; // 存储堆的数组 private int size; // 元素个数 private final Comparator comparator; // 比较器null表示自然排序 private static final int DEFAULT_INITIAL_CAPACITY 11; // 默认初始容量 }2. 入队offer ()源码public boolean offer(E e) { if (e null) throw new NullPointerException(); // 不允许null元素 modCount; int i size; if (i queue.length) grow(i 1); // 扩容 size i 1; if (i 0) queue[0] e; // 队列空直接作为堆顶 else siftUp(i, e); // 上浮调整 return true; } // 扩容逻辑 private void grow(int minCapacity) { int oldCapacity queue.length; // 扩容规则容量64时翻倍≥64时扩容50% int newCapacity oldCapacity ((oldCapacity ) ? (oldCapacity 2) : (oldCapacity 1)); if (newCapacity - MAX_ARRAY_SIZE 0) newCapacity hugeCapacity(minCapacity); queue Arrays.copyOf(queue, newCapacity); } // 上浮操作根据是否有比较器选择不同实现 private void siftUp(int k, E x) { if (comparator ! null) siftUpUsingComparator(k, x); // 自定义比较器 else siftUpComparable(k, x); // 自然排序 } // 自然排序的上浮 private void siftUpComparable(int k, E x) { Comparable super E key (Comparable x; while (k 0) { int parent (k - 1) 1; // 父节点索引等价于(k-1)/2无符号右移 Object e queue[parent]; if (key.compareTo((E) e) 0) break; // 父节点优先级更高停止上浮 queue[k] e; // 父节点下沉 k parent; // 继续向上比较 } queue[k] key; }3. 出队poll ()源码public E poll() { if (size 0) return null; int s --size; modCount; E result (E) queue[0]; // 堆顶元素结果 E x (E) queue[s]; // 末尾元素 queue[s] null; // 清空末尾 if (s ! 0) siftDown(0, x); // 下沉调整 return result; } // 下沉操作根据是否有比较器选择不同实现 private void siftDown(int k, E x) { if (comparator ! null) siftDownUsingComparator(k, x); else siftDownComparable(k, x); } // 自然排序的下沉 private void siftDownComparable(int k, E x) { Comparable key (Comparable? super E) x; int half size 1; // 非叶子节点的最大索引叶子节点无需下沉 while (k half) { int left (k 1) 1; // 左子节点索引 int right left 1; // 右子节点索引 Object c queue[left]; // 左子节点 // 选择左右子节点中优先级更高的小顶堆选更小的 if (right able).compareTo((E) queue[right]) 0) c queue[right]; if (key.compareTo((E) c) 0) break; // 当前节点优先级更高停止下沉 queue[k] c; // 子节点上浮 k left; // 继续向下比较 } queue[k] key; }4. 关键源码总结不允许存储null元素offer()直接抛空指针扩容规则容量 64 时翻倍 2≥64 时扩容 50%排序依赖Comparable自然排序或Comparator自定义排序核心操作offer()和poll()的时间复杂度为O(log n)堆的高度是log2(n)。五、并发安全的优先级队列PriorityBlockingQueuePriorityQueue是线程不安全的多线程环境下需使用java.util.concurrent.PriorityBlockingQueue阻塞优先级队列它的核心特性基于PriorityQueue实现保留优先级排序特性线程安全通过ReentrantLock保证入队 / 出队操作的原子性阻塞特性队列为空时take()会阻塞直到有元素队列满时有界put()会阻塞直到有空闲位置默认无界可指定容量4.无界特性默认初始容量 11满时自动扩容与PriorityQueue一致。核心使用示例import java.util.concurrent.PriorityBlockingQueue; public class PriorityBlockingQueueDemo { public static void main(String[] args) throws InterruptedException { // 大顶堆自定义比较器 PriorityBlockingQueue new PriorityBlockingQueue((a, b) - b - a); // 生产者线程入队 new Thread(() - { try { pbq.put(3); pbq.put(1); pbq.put(2); } catch (InterruptedException e) { Thread.currentThread().interrupt(); } }).start(); // 消费者线程出队 new Thread(() - { try { System.out.println(pbq.take()); // 输出3 System.out.println(pbq.take()); // 输出2 System.out.println(pbq.take()); // 输出1 } catch (InterruptedException e) { Thread.currentThread().interrupt(); } }).start(); } }六、手写优先级队列模拟实现基于二叉堆的原理手写一个简易版优先级队列支持自然排序和自定义比较器import java.util.Arrays; import java.util.Comparator; public class MyPriorityQueue private Object[] queue; // 存储堆的数组 private int size; // 元素个数 private Comparator E comparator; // 比较器 private static final int DEFAULT_CAPACITY 11; // 默认初始容量 // 构造方法1默认容量自然排序 public MyPriorityQueue() { this(DEFAULT_CAPACITY, null); } // 构造方法2指定容量自然排序 public MyPriorityQueue(int initialCapacity) { this(initialCapacity, null); } // 构造方法3指定容量自定义比较器 public MyPriorityQueue(int initialCapacity, Comparator? super E comparator) { if (initialCapacity throw new IllegalArgumentException(初始容量不能小于1); this.queue new Object[initialCapacity]; this.comparator comparator; } // 入队 public boolean offer(E e) { if (e null) throw new NullPointerException(元素不能为null); // 扩容判断 if (size queue.length) grow(); // 插入元素并上浮 if (size 0) queue[0] e; else siftUp(size, e); size; return true; } // 出队 public E poll() { if (size 0) return null; size--; E top (E) queue[0]; // 堆顶元素 E last (E) queue[size]; // 末尾元素 queue[size] null; // 清空末尾 // 下沉调整 if (size 0) siftDown(0, last); return top; } // 查看堆顶 public E peek() { return size 0 ? null : (E) queue[0]; } // 扩容 private void grow() { int oldCapacity queue.length; // 扩容规则4时翻倍2≥64时扩容50% int newCapacity oldCapacity (oldCapacity ? (oldCapacity 2) : (oldCapacity 1)); queue Arrays.copyOf(queue, newCapacity); } // 上浮操作 private void siftUp(int k, E x) { if (comparator ! null) siftUpWithComparator(k, x); else siftUpWithComparable(k, x); } // 自然排序的上浮 private void siftUpWithComparable(int k, E x) { Comparable super E key (Comparable x; while (k 0) { int parent (k - 1) 1; // 父节点索引 E parentVal (E) queue[parent]; if (key.compareTo(parentVal) 0) break; // 父节点优先级更高停止 // 父节点下沉 queue[k] parentVal; k parent; } queue[k] key; } // 自定义比较器的上浮 private void siftUpWithComparator(int k, E x) { while (k 0) { int parent (k - 1) 1; E parentVal (E) queue[parent]; if (comparator.compare(x, parentVal) 0) break; queue[k] parentVal; k parent; } queue[k] x; } // 下沉操作 private void siftDown(int k, E x) { if (comparator ! null) siftDownWithComparator(k, x); else siftDownWithComparable(k, x); } // 自然排序的下沉 private void siftDownWithComparable(int k, E x) { Comparable? super E key (Comparable) x; int half size 1; // 非叶子节点的最大索引 while (k int left (k 1; // 左子节点 int right left 1; // 右子节点 E minChild (E) queue[left]; // 选择左右子节点中优先级更高的 if (right size ((Comparable super E) minChild).compareTo((E) queue[right]) 0) minChild (E) queue[right]; if (key.compareTo(minChild) 0) break; // 当前节点优先级更高停止 queue[k] minChild; k left; } queue[k] key; } // 自定义比较器的下沉 private void siftDownWithComparator(int k, E x) { int half size 1; while (k half) { int left (k 1) 1; int right left 1; E minChild (E) queue[left]; if (right comparator.compare(minChild, (E) queue[right]) 0) minChild (E) queue[right]; if (comparator.compare(x, minChild) 0) break; queue[k] minChild; k left; } queue[k] x; } // 辅助方法获取元素个数 public int size() { return size; } // 测试 public static void main(String[] args) { // 测试大顶堆 MyPriorityQueueInteger maxHeap new MyPriorityQueue, b) - b - a); maxHeap.offer(5); maxHeap.offer(2); maxHeap.offer(8); maxHeap.offer(1); System.out.println(大顶堆出队顺序); while (maxHeap.size() 0) { System.out.print(maxHeap.poll() ); // 输出8 5 2 1 } // 测试小顶堆自然排序 MyPriorityQueue new MyPriorityQueue(); minHeap.offer(5); minHeap.offer(2); minHeap.offer(8); minHeap.offer(1); System.out.println(\n小顶堆出队顺序); while (minHeap.size() 0) { System.out.print(minHeap.poll() ); // 输出1 2 5 8 } } }七、优先级队列的常见问题与注意事项1. 线程安全问题PriorityQueue线程不安全多线程同时入队 / 出队会导致数据错乱并发场景必须用PriorityBlockingQueue阻塞或手动加锁synchronized/Lock。2. 无界队列的 OOM 风险PriorityQueue和PriorityBlockingQueue默认无界若入队速度远大于出队速度会导致元素堆积最终 OOM解决方案使用PriorityBlockingQueue时指定容量有界配合拒绝策略需自定义。3. 元素排序的一致性若元素是自定义对象需保证Comparable的compareTo()方法或Comparator的compare()方法逻辑一致否则会导致排序异常例compareTo()返回this.age - o.age表示升序若中途修改为o.age - this.age会破坏堆结构。4. 遍历无序问题PriorityQueue的iterator()遍历结果是无序的仅按数组存储顺序若需有序遍历需通过poll()逐个取出会删除元素或复制到数组后排序。八、总结面试必背优先级队列按元素优先级排序出队取优先级最高元素底层是二叉堆小顶堆默认核心操作入队siftUp、出队siftDown时间复杂度O(log n)Java 实现PriorityQueue无界、线程不安全支持自然排序 / 自定义比较器PriorityBlockingQueue无界 / 有界、线程安全、阻塞适用于并发场景关键考点二叉堆的存储结构与核心操作自定义比较器实现大顶堆线程安全的替代方案手写优先级队列堆的上浮 / 下沉实战场景TopK 问题、任务调度、最短路径算法等。