Java中PriorityQueue的用途和性能深度剖析

哈喽，各位小伙伴们，你们好呀，我是喵手。运营社区：C站/掘金/腾讯云；欢迎大家常来逛逛

今天我要给大家分享一些自己日常学习到的一些知识点，并以文字的形式跟大家一起交流，互相学习，一个人虽可以走的更快，但一群人可以走的更远。

我是一名后端开发爱好者，工作日常接触到最多的就是Java语言啦，所以我都尽量抽业余时间把自己所学到所会的，通过文章的形式进行输出，希望以这种方式帮助到更多的初学者或者想入门的小伙伴们，同时也能对自己的技术进行沉淀，加以复盘，查缺补漏。

小伙伴们在批阅的过程中，如果觉得文章不错，欢迎点赞、收藏、关注哦。三连即是对作者我写作道路上最好的鼓励与支持！

前言

在开发中，我们经常需要对元素进行排序，并且可以快速访问最小或最大元素。这个时候，PriorityQueue就成了我们的不二选择。PriorityQueue是一个基于优先级堆的无界优先级队列。根据不同的构造函数，可以将PriorityQueue定义为小根堆和大根堆。

摘要

本文将重点介绍Java中的PriorityQueue类。我们将深入探讨PriorityQueue类的用法，它的优缺点，以及一些常见的应用场景，最主要的还是会通过实例结合知识点给大家侧面剖析，理论结合实践，以保障大家能够理解的更为透彻。

PriorityQueue

简介

PriorityQueue可以被认为是一个数组，但它具有一些额外的限制。首先，PriorityQueue的大小是固定的，而且只能在初始化的时候设置。其次，PriorityQueue不允许使用索引来访问元素，因此我们不能查看PriorityQueue中的第k个元素。相反，PriorityQueue中的元素都是按照优先级排列的，并且可以使用poll()方法快速获取优先级最高的元素。

源代码解析

public class PriorityQueue<E extends Comparable<? super E>> extends AbstractQueue<E> implements Serializable {
    //...
}

从上面的代码可以看出，PriorityQueue是一个继承了AbstractQueue类并实现了Serializable接口的泛型类。在Java中，泛型是一种强类型编程机制，它可以在编译时对类型进行检查并确定类型安全。在PriorityQueue中，使用了泛型<E extends Comparable<? super E>>来限制元素类型，确保元素类型实现了Comparable接口，也就是说元素可以进行比较。

在这里插入图片描述

PriorityQueue中有一个关键的成员变量，即堆数组：

private transient Object[] queue;

在PriorityQueue中，堆数组实际上是用来存储所有元素的。堆数组中的下标从1开始，因为堆数组中的第一个元素在下标1处。当我们添加一个元素时，它将被添加到堆数组的最后一个位置。然后，我们必须保证堆数组中元素的顺序是按照优先级来排序的，如果不是，我们就需要重新排列堆数组。在实现堆排序时，我们通常使用一组siftUp()和siftDown()方法（也称为percolateUp()和percolateDown()）。

siftUp()方法

siftUp()方法是将刚添加的元素上浮到合适的位置。它的实现方法类似于冒泡排序方法。当我们添加一个元素时，它将被添加到堆数组的末尾，然后我们不断地比较它和它的父节点，并交换它们的位置，直到它的父节点小于等于它或者到达根节点位置。

在这里插入图片描述

siftDown()方法

siftDown()方法是将根节点下沉到合适的位置。当我们删除一个元素时，它会被堆数组的最后一个元素替换，然后我们将根节点下沉到合适的位置以维护堆的有序性。与siftUp()方法类似，siftDown()方法不断地比较当前节点和它的子节点，并交换它们的位置，直到当前节点小于等于最小的子节点或子节点都为空。

应用场景案例

PriorityQueue可以用于需要对元素按照优先级排序的场景。以下是一些使用PriorityQueue的常见场景：

模拟任务调度系统：可以将所有任务按照优先级放入PriorityQueue中，并使用poll()方法获取下一个要执行的任务。
合并多个有序数组：可以将多个有序数组的第一个元素放入PriorityQueue中，并且每次从PriorityQueue中取出最小的元素，直到PriorityQueue为空。
实现Dijkstra最短路径算法：可以将所有顶点按照距离起点的距离放入PriorityQueue中，并使用poll()方法获取到达下一个顶点的最短路径。

优缺点分析

优点：

PriorityQueue可以高效地维护元素的有序性，它内部使用堆排序算法来维护元素的顺序。
PriorityQueue可以用于需要快速访问最小或最大元素的场景。
PriorityQueue可以通过指定Comparator来按照自定义的优先级来进行排序。

缺点：

PriorityQueue不允许使用索引来访问元素，因此我们不能查看PriorityQueue中的第k个元素。
PriorityQueue的大小是固定的，而且只能在初始化的时候设置。
PriorityQueue不是线程安全的，如果需要线程安全的优先级队列，可以使用ConcurrentPriorityQueue类。

类代码方法介绍

构造方法

PriorityQueue()：创建一个空的PriorityQueue，初始容量为11，按照元素的自然顺序进行排序。
PriorityQueue(int initialCapacity)：创建一个空的PriorityQueue，初始容量为initialCapacity，按照元素的自然顺序进行排序。
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)：创建一个空的PriorityQueue，初始容量为initialCapacity，按照指定的comparator进行排序。
PriorityQueue(Collection<? extends E> c)：创建一个包含c中所有元素的PriorityQueue，按照元素的自然顺序进行排序。
PriorityQueue(PriorityQueue<? extends E> c)：创建一个包含c中所有元素的PriorityQueue，按照PriorityQueue中元素的自然顺序进行排序。
PriorityQueue(SortedSet<? extends E> c)：创建一个包含c中所有元素的PriorityQueue，按照c的比较顺序进行排序。

方法

boolean add(E e)：添加指定元素到PriorityQueue中。
void clear()：从PriorityQueue中移除所有元素。
Comparator<? super E> comparator()：返回PriorityQueue中元素的排序方式。
boolean contains(Object o)：检查PriorityQueue中是否包含指定的元素。
Iterator iterator()：返回PriorityQueue中元素的迭代器，按照元素的自然顺序进行排序。
boolean offer(E e)：添加指定元素到PriorityQueue中。
E peek()：返回PriorityQueue中的第一个元素，如果PriorityQueue为空，则返回null。
E poll()：移除并返回PriorityQueue中的第一个元素，如果PriorityQueue为空，则返回null。
boolean remove(Object o)：从PriorityQueue中移除指定元素。
int size()：返回PriorityQueue中的元素个数。
Object[] toArray()：将PriorityQueue中的元素转换为数组。
T[] toArray(T[] a)：将PriorityQueue中的元素转换为指定类型的数组。

测试用例

下面是一些测试代码，测试PriorityQueue的基本功能：

测试代码演示

package com.example.javase.collection;

import java.util.PriorityQueue;

/**
 * @Author ms
 * @Date 2023-10-24 18:47
 */
public class PriorityQueueTest {

    public static void main(String[] args) {
        // 创建一个PriorityQueue
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 添加元素
        pq.offer(1);
        pq.offer(3);
        pq.offer(2);

        // 获取元素
        System.out.println(pq.poll()); // 1
        System.out.println(pq.poll()); // 2
        System.out.println(pq.poll()); // 3

        // 检查是否为空
        System.out.println(pq.isEmpty()); // true
    }
}

测试结果

根据如上测试用例，本地测试结果如下，仅供参考，你们也可以自行修改测试用例或者添加更多的测试数据或测试方法，进行熟练学习以此加深理解。

在这里插入图片描述

代码分析

根据如上测试用例，在此我给大家进行深入详细的解读一下测试代码，以便于更多的同学能够理解并加深印象。
如上测试用例演示了使用Java中的PriorityQueue类进行优先级队列的操作。在代码中，首先创建了一个PriorityQueue对象pq，然后通过调用pq.offer()方法添加了三个整数元素1、3和2。接着调用pq.poll()方法获取队列中的元素，由于PriorityQueue是一个优先级队列，因此获取的元素将会按照从小到大的顺序依次弹出，即先弹出1，再弹出2，最后弹出3。最后通过pq.isEmpty()方法检查队列是否为空，输出结果为true，证明队列已经为空。

全文小结

本文介绍了Java中的PriorityQueue类，它是一个基于优先级堆的无界优先级队列。我们深入探讨了PriorityQueue类的源代码解析，它的优缺点，以及一些常见的应用场景。我们还介绍了PriorityQueue类的构造方法和方法，并提供了一些测试用例。在开发中，我们可以用PriorityQueue来模拟任务调度系统、合并多个有序数组以及实现Dijkstra最短路径算法等场景。