Java PriorityQueue如何实现优先级队列

Java中PriorityQueue基于最小堆实现，底层用数组存储并维护堆性质；插入元素时通过上浮操作保持堆序，时间复杂度O(log n)；删除队头元素后通过下沉调整，同样O(log n)；支持自定义Comparator实现最大堆或特定排序；非线程安全，适用于任务调度等场景。

Java 中的 PriorityQueue 是通过二叉堆（Binary Heap）结构实现优先级队列的，具体来说是最小堆（Min-Heap），也就是说队列头部是最小的元素。如果指定了比较器，则根据自定义规则决定优先级。

底层数据结构：数组 + 堆化操作

PriorityQueue 内部使用一个动态扩容的 Object 数组来存储元素。这个数组按照完全二叉树的层次遍历方式组织，逻辑上形成一个堆结构：

• 根节点（索引0）是当前优先级最高的元素（默认最小）
• 对于索引为 i 的节点，其左子节点在 2*i+1，右子节点在 2*i+2，父节点在 (i-1)/2
• 插入和删除后会通过“上浮”（sift-up）和“下沉”（sift-down）操作维持堆性质

添加元素：offer() 方法

当调用 offer() 添加元素时，执行以下步骤：

• 将新元素放到数组末尾
• 与其父节点比较，若优先级更高（更小或按比较器规则更靠前），则交换位置
• 重复向上调整，直到满足堆性质 —— 这个过程叫上浮（Sift-Up）

时间复杂度为 O(log n)。

立即学习“Java免费学习笔记（深入）”；

取出元素：poll() 方法

调用 poll() 取出队头元素时：

先见AI

数据为基，先见未见

95

查看详情

• 取出数组第一个元素并返回
• 将最后一个元素移到队首
• 从根开始向下比较，与左右子节点中优先级更高的交换
• 重复此过程直到堆结构恢复 —— 这个过程叫下沉（Sift-Down）

时间复杂度同样为 O(log n)。

构造函数支持自定义优先级

默认情况下，元素需实现 Comparable 接口。也可以传入 Comparator 来定义排序规则：

这使得你可以控制哪个元素具有更高优先级，比如实现最大堆、按对象字段排序等。

基本上就这些。PriorityQueue 不是线程安全的，若需并发环境使用，应考虑 PriorityBlockingQueue。它保证了插入和删除的高效性，适合用于任务调度、合并 K 个有序流等场景。

以上就是Java PriorityQueue如何实现优先级队列的详细内容，更多请关注php中文网其它相关文章！