JavaPriorityQueue使用详解与实战教程

本教程深入解析Java优先队列PriorityQueue的使用。PriorityQueue是一种基于堆数据结构的特殊队列，它能保证每次取出的是优先级最高的元素。本文将详细介绍PriorityQueue的构造函数，包括默认容量、自定义比较器以及从集合初始化的方法。同时，深入讲解offer/add、poll/remove、peek、size、contains等常用方法，并分析它们的时间复杂度。此外，本文还展示了如何通过Comparator接口自定义排序规则，以及PriorityQueue与TreeSet的区别，助你理解其底层堆结构和适用场景，掌握Java优先队列的应用技巧。

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

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

解决方案

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

1. 构造函数：

   • PriorityQueue()：创建一个具有默认初始容量（11）的 PriorityQueue，并根据其元素的自然顺序对其进行排序。
   • PriorityQueue(int initialCapacity)：创建一个具有指定初始容量的 PriorityQueue，并根据其元素的自然顺序对其进行排序。
   • PriorityQueue(Comparator comparator)：创建一个具有默认初始容量的 PriorityQueue，并根据指定的比较器对其元素进行排序。
   • PriorityQueue(int initialCapacity, Comparator comparator)：创建一个具有指定初始容量的 PriorityQueue，并根据指定的比较器对其元素进行排序。
   • PriorityQueue(Collection c)：创建一个包含指定集合中的元素的 PriorityQueue。
   • PriorityQueue(PriorityQueue c)：创建一个包含指定优先级队列中的元素的 PriorityQueue。
   • PriorityQueue(SortedSet c)：创建一个包含指定排序集合中的元素的 PriorityQueue。

2. 常用方法：

   
   • 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 适用于需要维护有序集合的场景，例如字典、索引等。

简单来说，如果只需要获取优先级最高的元素，使用 PriorityQueue 效率更高。如果需要维护一个完全有序的集合，使用 TreeSet 更合适。

到这里，我们也就讲完了《JavaPriorityQueue使用详解与实战教程》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于时间复杂度,堆,TreeSet,comparator,PriorityQueue的知识点！