异常教程

java priorityqueue（保姆级教程）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战(已更新的所有项目都能学习) / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

  • 新开坑项目:《Spring AI 项目实战》 正在持续爆肝中，基于 Spring AI + Spring Boot 3.x + JDK 21...， 点击查看 ;
  • 《从零手撸：仿小红书（微服务架构）》 已完结，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;演示链接： http://116.62.199.48:7070 ;
  • 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 100w+ 字，讲解图 4013+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3700+ 小伙伴加入学习 ，欢迎点击围观

在 Java 编程中，集合框架提供了多种数据结构，其中 PriorityQueue 是一个功能强大且应用场景广泛的类。它基于优先堆（priority heap）实现，能够根据元素的优先级动态调整顺序，从而高效地获取当前队列中的最高（或最低）优先级元素。对于编程初学者和中级开发者而言，理解 PriorityQueue 的底层原理和实际应用，不仅能提升代码编写能力，还能在算法设计和系统优化中发挥重要作用。本文将从基础概念、实现原理、代码示例及常见问题等角度，深入浅出地讲解这一主题。

一、优先队列的核心原理

1.1 优先队列的定义与特性

优先队列（Priority Queue）是一种特殊的队列结构，它与普通队列（如 LinkedList 实现的 Queue）最大的区别在于：元素的出队顺序并非遵循严格的“先进先出”（FIFO），而是根据元素的优先级（priority）来决定。优先级高的元素会被优先弹出。

例如，想象一个医院的急诊室：患者根据伤势的严重程度被分到不同优先级，医生会优先救治最危急的患者，而不是按到达顺序处理。这种场景下，优先队列就是理想的实现工具。

在 Java 中，PriorityQueue 默认按照元素的自然顺序（natural order）进行排序，若元素未实现 Comparable 接口，则需要通过 Comparator 自定义排序规则。

1.2 基于堆结构的实现

PriorityQueue 的内部实现基于二叉堆（通常为最小堆）。二叉堆是一个完全二叉树，满足以下性质：

  • 父节点的优先级 ≤ 子节点的优先级（最小堆）；
  • 或父节点的优先级 ≥ 子节点的优先级（最大堆）。

Java 的 PriorityQueue 默认是最小堆，即队列头部（peek() 或 poll() 获取的元素）是当前队列中优先级最低的元素。若需实现最大堆，可以通过反向排序或自定义 Comparator 来调整。

形象比喻：堆结构的“金字塔”

可以将二叉堆想象成一座金字塔：

  • 塔顶的元素是当前优先级最高的（或最低的）；
  • 每一层的元素都比下一层的优先级更高（或更低）。
    当插入新元素时，它会从金字塔的底部开始“冒泡”，直到找到合适的位置；而弹出顶部元素后，金字塔会重新调整结构以维持堆的性质。

二、如何使用 Java Priority Queue

2.1 基础操作与代码示例

2.1.1 创建优先队列

可以通过以下方式创建 PriorityQueue：

// 默认最小堆（按元素自然顺序排序）  
PriorityQueue<Integer> minHeap = new PriorityQueue<>();  

// 自定义排序规则（例如最大堆）  
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

2.1.2 常用方法

  • add(E e) 或 offer(E e)：将元素插入队列。
  • peek()：获取但不移除队列头部元素。
  • poll()：获取并移除队列头部元素。
  • isEmpty()：判断队列是否为空。
  • size()：获取队列元素数量。

示例代码：

PriorityQueue<String> queue = new PriorityQueue<>();  
queue.offer("Apple");  
queue.offer("Banana");  
queue.offer("Cherry");  

System.out.println(queue.peek()); // 输出 "Apple"（按字母顺序，A < B < C）  
System.out.println(queue.poll()); // 移除并返回 "Apple"

2.2 自定义优先级规则

若元素类型未实现 Comparable，或需要覆盖默认排序规则，可通过 Comparator 实现。例如：

场景：根据订单金额从高到低排序。

class Order {  
    private String id;  
    private double amount;  
    // 构造方法、getter/setter 省略  
}  

PriorityQueue<Order> orderQueue = new PriorityQueue<>((o1, o2) ->  
    Double.compare(o2.getAmount(), o1.getAmount())  
);

三、实际案例与应用场景

3.1 案例 1：任务调度系统

假设需要实现一个任务调度器，按优先级执行任务：

class Task implements Comparable<Task> {  
    private int priority;  
    private String description;  

    // 构造方法、getter/setter 省略  

    @Override  
    public int compareTo(Task other) {  
        return Integer.compare(this.priority, other.priority); // 小优先级先执行  
    }  
}  

public class Scheduler {  
    public static void main(String[] args) {  
        PriorityQueue<Task> taskQueue = new PriorityQueue<>();  

        taskQueue.add(new Task(2, "Low Priority Task"));  
        taskQueue.add(new Task(1, "High Priority Task"));  

        while (!taskQueue.isEmpty()) {  
            Task currentTask = taskQueue.poll();  
            System.out.println("Executing: " + currentTask.getDescription());  
        }  
    }  
}

输出结果：

Executing: High Priority Task  
Executing: Low Priority Task

3.2 案例 2：求第 K 大元素

在数组中找到第 K 大的元素，可以通过优先队列优化时间复杂度：

public static int findKthLargest(int[] nums, int k) {  
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();  

    for (int num : nums) {  
        minHeap.offer(num);  
        if (minHeap.size() > k) {  
            minHeap.poll(); // 保持堆大小为 k  
        }  
    }  
    return minHeap.peek(); // 堆顶即第 K 大元素  
}

此方法的时间复杂度为 (O(n \log k))，比排序法（(O(n \log n))）更高效。

四、常见问题与注意事项

4.1 默认行为与自定义排序的冲突

若元素同时实现了 Comparable 和通过构造器传入 Comparator，后者会覆盖前者。例如：

// Order 类已实现 Comparable（按金额升序）  
PriorityQueue<Order> queue = new PriorityQueue<>((o1, o2) ->  
    Double.compare(o1.getAmount(), o2.getAmount())  // 覆盖自然排序  
);

4.2 线程安全性

PriorityQueue 不是线程安全的。在多线程环境下，若需并发访问，可通过 Collections.synchronizedQueue() 包装，或使用 ConcurrentHashMap 等线程安全的集合。

4.3 性能特性

  • 插入操作（add/offer）的时间复杂度为 (O(\log n))；
  • 获取/删除头部元素（peek/poll）的时间复杂度为 (O(1))；
  • 检索元素（如 contains）的时间复杂度为 (O(n))，因其底层结构不支持快速查找。

五、与其他队列的对比

5.1 与 LinkedList 的区别

LinkedList 实现的 Queue 遵循严格的 FIFO，而 PriorityQueue 根据优先级动态调整顺序。例如：

Queue<String> fifoQueue = new LinkedList<>();  
fifoQueue.add("A");  
fifoQueue.add("B");  
System.out.println(fifoQueue.poll()); // 输出 "A"  

PriorityQueue<String> priorityQueue = new PriorityQueue<>();  
priorityQueue.add("B");  
priorityQueue.add("A");  
System.out.println(priorityQueue.poll()); // 输出 "A"（按字母顺序）

5.2 与 ArrayDeque 的对比

ArrayDeque 是一个通用的双端队列，支持快速插入和删除操作，但不提供优先级管理功能。若需按优先级排序，仍需结合 PriorityQueue。

结论

Java Priority Queue 是一种灵活且高效的队列实现，适用于需要动态优先级管理的场景。通过理解其基于堆结构的底层原理，开发者可以更合理地设计算法和系统逻辑。无论是任务调度、资源分配，还是优化复杂问题的时间复杂度，PriorityQueue 都能提供简洁而强大的解决方案。

在实际开发中，建议根据具体需求选择默认排序或自定义 Comparator，并注意线程安全性和性能边界。掌握这一工具，将帮助开发者在 Java 生态中更从容地应对各类挑战。

最新发布

查看更多文章