当前位置： 技术文章>> Java中的PriorityQueue如何实现优先队列？

文章标题：Java中的PriorityQueue如何实现优先队列？
  • 文章分类: 后端
  • 9610 阅读

在Java中，PriorityQueue 是一个基于优先级堆的无界优先级队列。它不允许使用 null 元素，并且自然排序或者通过构造器提供的 Comparator 进行元素的排序。PriorityQueue 实现了 java.util.Queue 接口，但不是一个严格的先进先出（FIFO）队列，其元素按照指定的排序规则被移除。这种数据结构非常适合实现任务调度、优先级事件处理等场景。

PriorityQueue 的内部实现

PriorityQueue 实际上是通过一个基于数组的二叉堆来实现的。二叉堆是一种特殊的完全二叉树，其中每个父节点的值都大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。Java中的 PriorityQueue 默认实现是一个最小堆，这意味着队列的头部（即 peek() 或 poll() 方法返回的元素）是当前队列中最小（或根据提供的 Comparator 排序后最小）的元素。

二叉堆的数组表示

在二叉堆中，通常使用一维数组来存储堆的元素。给定数组中的某个位置 i，其父节点的位置是 (i - 1) / 2，左子节点的位置是 2 * i + 1，右子节点的位置是 2 * i + 2。这种简单的位置关系使得堆的操作（如插入、删除）变得高效。

核心操作

  1. 插入（offer(E e)）： 向 PriorityQueue 插入一个新元素时，首先将新元素添加到数组的末尾，然后执行上浮（sift-up）操作，即将其与父节点比较，如果违反了堆的性质（对于最小堆，即新元素小于其父节点），则与父节点交换位置，继续这个过程直到新元素到达正确的位置。

  2. 删除最小元素（poll()）： 从 PriorityQueue 移除并返回队列中的最小元素时，通常移除的是数组的第一个元素（即堆顶元素），然后将数组的最后一个元素移动到堆顶，并执行下沉（sift-down）操作，即将新的堆顶元素与其子节点比较，如果违反了堆的性质，则与较小的子节点交换位置，直到它到达正确的位置。

  3. 查找最小元素（peek()）： 返回队列中的最小元素但不移除它。这只是一个简单的数组访问操作，返回数组的第一个元素（即堆顶元素）。

PriorityQueue 的构造函数

PriorityQueue 提供了几个构造函数来创建不同配置的优先队列：

  • PriorityQueue()：使用元素的自然顺序来创建一个空的优先队列。元素必须实现 Comparable 接口。
  • PriorityQueue(Collection<? extends E> c)：根据给定集合元素的自然顺序创建一个优先队列。同样，元素必须实现 Comparable 接口。
  • PriorityQueue(int initialCapacity)：创建一个空的优先队列，并指定其初始容量。
  • PriorityQueue(int initialCapacity, boolean naturalOrder)：创建一个具有指定初始容量的空优先队列，并根据参数决定是否使用元素的自然顺序。
  • PriorityQueue(Comparator<? super E> comparator)：根据提供的 Comparator 创建一个空的优先队列。元素不需要实现 Comparable 接口。
  • PriorityQueue(Collection<? extends E> c, Comparator<? super E> comparator)：根据给定的集合和 Comparator 创建一个优先队列。

PriorityQueue 的使用示例

下面是一个使用 PriorityQueue 的简单示例，展示了如何创建一个最小堆，并向其中添加元素，然后移除并打印最小元素：

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 使用自然顺序创建一个PriorityQueue
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 向队列中添加元素
        pq.offer(10);
        pq.offer(1);
        pq.offer(5);
        pq.offer(20);

        // 移除并打印队列中的最小元素
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 输出: 1, 5, 10, 20
        }

        // 使用自定义比较器创建一个PriorityQueue
        PriorityQueue<String> pqWithComparator = new PriorityQueue<>((s1, s2) -> s2.compareTo(s1));

        // 向队列中添加字符串
        pqWithComparator.offer("Java");
        pqWithComparator.offer("Python");
        pqWithComparator.offer("C++");

        // 移除并打印队列中的最大元素（因为使用了反向比较器）
        while (!pqWithComparator.isEmpty()) {
            System.out.println(pqWithComparator.poll()); // 输出: C++, Python, Java
        }
    }
}

PriorityQueue 的性能特点

  • 插入操作：时间复杂度为 O(log n)，其中 n 是队列中的元素数量。在最坏的情况下，新元素需要上浮到堆的顶部。
  • 删除最小元素：时间复杂度同样是 O(log n)，因为需要执行下沉操作来调整堆。
  • 查找最小元素：时间复杂度为 O(1)，因为它只是简单地返回堆顶元素。

总结

PriorityQueue 是 Java 中的一个非常有用的数据结构，它利用二叉堆高效地实现了元素的优先排序。无论是自然排序还是通过自定义比较器排序，PriorityQueue 都提供了一种灵活且高效的方式来处理具有优先级的数据。在需要频繁进行插入和删除最小（或最大）元素的操作时，PriorityQueue 是一个很好的选择。通过码小课（一个专注于编程教育的网站），你可以深入学习更多关于 PriorityQueue 和其他 Java 数据结构的知识，进一步提升你的编程技能。

推荐文章