如何在Java中使用PriorityQueue Java优先队列用法详解-java教程-PHP中文网

如何在Java中使用PriorityQueue Java优先队列用法详解

雪夜

发布： 2025-07-16 16:29:02

原创

379人浏览过

java中的priorityqueue是一种基于堆实现的优先队列，其核心特性是每次取出优先级最高的元素。1. 它提供了多种构造函数，包括默认容量和排序方式、指定容量、自定义比较器以及从集合初始化；2. 常用方法如offer/add插入元素、poll/remove移除元素、peek查看队首、size获取大小、contains检查是否存在，其中offer更安全，poll和remove时间复杂度为o(log n)，peek和size为o(1)，contains为o(n)；3. 可通过实现comparator接口自定义排序规则，并在构造时传入比较器；4. 与treeset不同，priorityqueue底层是堆，只保证队首有序，而treeset基于红黑树，所有元素有序且支持索引，但两者均不允许null元素，适用场景各有侧重。

如何在Java中使用PriorityQueue Java优先队列用法详解

Java中的PriorityQueue是一种特殊的队列，它允许我们按照元素的优先级来处理它们。简单来说，你可以把它想象成一个自动排序的队列，每次取出的是优先级最高的元素。

PriorityQueue的本质是一个堆（通常是小根堆），这意味着队列中的元素总是按照某种顺序排列，保证队首元素是最小（或最大，取决于你的比较器）。

解决方案

使用PriorityQueue的关键在于理解它的构造函数和常用方法。

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

构造函数：
- PriorityQueue()：创建一个具有默认初始容量（11）的 PriorityQueue，并根据其元素的自然顺序对其进行排序。
- PriorityQueue(int initialCapacity)：创建一个具有指定初始容量的 PriorityQueue，并根据其元素的自然顺序对其进行排序。
- PriorityQueue(Comparator<? super E> comparator)：创建一个具有默认初始容量的 PriorityQueue，并根据指定的比较器对其元素进行排序。
- PriorityQueue(int initialCapacity, Comparator<? super E> comparator)：创建一个具有指定初始容量的 PriorityQueue，并根据指定的比较器对其元素进行排序。
- PriorityQueue(Collection<? extends E> c)：创建一个包含指定集合中的元素的 PriorityQueue。
- PriorityQueue(PriorityQueue<? extends E> c)：创建一个包含指定优先级队列中的元素的 PriorityQueue。
- PriorityQueue(SortedSet<? extends E> c)：创建一个包含指定排序集合中的元素的 PriorityQueue。
常用方法：

AppMall应用商店
AI应用商店，提供即时交付、按需付费的人工智能应用服务

56

查看详情
- add(E e) / offer(E e)：将指定的元素插入此优先级队列。offer 通常更安全，因为它在队列满时返回 false 而不是抛出异常。
- peek()：检索但不移除此队列的头，如果此队列为空，则返回 null。
- poll()：检索并移除此队列的头，如果此队列为空，则返回 null。
- remove(Object o)：从此队列中移除指定元素的单个实例（如果存在）。
- contains(Object o)：如果此队列包含指定元素，则返回 true。
- size()：返回此队列中的元素数量。
- clear()：从此队列中移除所有元素。
- iterator(): 返回在此队列中的元素上进行迭代的迭代器。

示例代码：

import java.util.PriorityQueue;
import java.util.Comparator;

public class PriorityQueueExample {

    public static void main(String[] args) {
        // 使用默认自然顺序的 PriorityQueue (小根堆)
        PriorityQueue<Integer> pq1 = new PriorityQueue<>();
        pq1.add(5);
        pq1.add(1);
        pq1.add(10);
        pq1.add(3);

        System.out.println("Default PriorityQueue:");
        while (!pq1.isEmpty()) {
            System.out.print(pq1.poll() + " "); // 输出: 1 3 5 10
        }
        System.out.println();

        // 使用自定义 Comparator 的 PriorityQueue (大根堆)
        PriorityQueue<Integer> pq2 = new PriorityQueue<>(Comparator.reverseOrder());
        pq2.add(5);
        pq2.add(1);
        pq2.add(10);
        pq2.add(3);

        System.out.println("Custom Comparator PriorityQueue:");
        while (!pq2.isEmpty()) {
            System.out.print(pq2.poll() + " "); // 输出: 10 5 3 1
        }
        System.out.println();

        // 使用自定义对象的 PriorityQueue
        PriorityQueue<Task> taskQueue = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority));
        taskQueue.add(new Task("Task A", 3));
        taskQueue.add(new Task("Task B", 1));
        taskQueue.add(new Task("Task C", 2));

        System.out.println("Task PriorityQueue:");
        while (!taskQueue.isEmpty()) {
            System.out.println(taskQueue.poll());
        }
    }

    static class Task {
        private String name;
        private int priority;

        public Task(String name, int priority) {
            this.name = name;
            this.priority = priority;
        }

        public String getName() {
            return name;
        }

        public int getPriority() {
            return priority;
        }

        @Override
        public String toString() {
            return "Task{" +
                    "name='" + name + '\'' +
                    ", priority=" + priority +
                    '}';
        }
    }
}

登录后复制

PriorityQueue 的时间复杂度是多少？

offer(E e) 和 add(E e): O(log n)，其中 n 是队列中的元素数量。这是因为插入元素后需要调整堆结构。
poll() 和 remove(Object o): O(log n)，其中 n 是队列中的元素数量。移除元素后也需要调整堆结构。
peek(): O(1)，因为只是查看堆顶元素，不需要调整堆。
size(): O(1)，直接返回队列的大小。
contains(Object o): O(n)，在最坏情况下需要遍历整个队列来查找元素。

如何自定义 PriorityQueue 的排序规则？

可以通过实现 Comparator 接口来定义自定义的排序规则。Comparator 接口允许你指定两个对象之间的比较方式。在创建 PriorityQueue 实例时，将自定义的 Comparator 传递给构造函数。

import java.util.PriorityQueue;
import java.util.Comparator;

public class CustomPriorityQueue {

    public static void main(String[] args) {
        // 自定义 Comparator，按照字符串长度降序排列
        Comparator<String> stringLengthComparator = (s1, s2) -> s2.length() - s1.length();

        PriorityQueue<String> stringQueue = new PriorityQueue<>(stringLengthComparator);
        stringQueue.add("apple");
        stringQueue.add("banana");
        stringQueue.add("kiwi");
        stringQueue.add("orange");

        System.out.println("Custom String PriorityQueue:");
        while (!stringQueue.isEmpty()) {
            System.out.println(stringQueue.poll()); // 输出: banana, orange, apple, kiwi
        }
    }
}

登录后复制

PriorityQueue 和 TreeSet 的区别是什么？

PriorityQueue 和 TreeSet 都是用于存储有序元素的集合，但它们在实现和使用上有一些关键区别：

底层数据结构： PriorityQueue 基于堆（通常是小根堆）实现，而 TreeSet 基于红黑树实现。
排序方式： PriorityQueue 只保证队首元素是最小（或最大）的，其他元素的顺序不确定。 TreeSet 则保证所有元素都是有序的。
是否允许 null 元素： PriorityQueue 不允许存储 null 元素，会抛出 NullPointerException。 TreeSet 也不允许存储 null 元素（在大多数实现中）。
时间复杂度： PriorityQueue 的 offer 和 poll 操作的时间复杂度为 O(log n)，peek 操作为 O(1)。 TreeSet 的 add、remove 和 contains 操作的时间复杂度都为 O(log n)。
应用场景： PriorityQueue 适用于需要频繁获取最小（或最大）元素的场景，例如任务调度、堆排序等。 TreeSet 适用于需要维护有序集合的场景，例如字典、索引等。