滚雪球学Java(70):深入理解Java中的PriorityQueue底层实现与源码分析

举报
bug菌 发表于 2024/03/18 13:39:34 2024/03/18
【摘要】 🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,助你一臂之力,带你早日登顶🚀,欢迎大家关注&&收藏!持续更新中,up!up!up!!

在这里插入图片描述

  咦咦咦,各位小可爱,我是你们的好伙伴——bug菌,今天又来给大家普及Java SE相关知识点了,别躲起来啊,听我讲干货还不快点赞,赞多了我就有动力讲得更嗨啦!所以呀,养成先点赞后阅读的好习惯,别被干货淹没了哦~

在这里插入图片描述


🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,助你一臂之力,带你早日登顶🚀,欢迎大家关注&&收藏!持续更新中,up!up!up!!

环境说明:Windows 10 + IntelliJ IDEA 2021.3.2 + Jdk 1.8

@[toc]

前言

  PriorityQueue是Java中一个非常常用的数据结构,它可以实现基于优先级的排序,常用于任务调度、事件处理等场景。本文将深入探讨Java中PriorityQueue的底层实现与源码分析,帮助读者更好地理解PriorityQueue的内部原理。

摘要

  本文将从PriorityQueue的定义、特性入手,逐步分析其底层实现、源码解析以及应用场景案例、优缺点分析等方面,全面深入地理解PriorityQueue。

PriorityQueue

概述

PriorityQueue的定义与特性

  在Java中,PriorityQueue是一个优先级队列,它是基于数组实现的,但是其中的元素不是按照插入顺序排列,而是按照元素的优先级进行排序。你可以将任意类型的对象插入PriorityQueue中,并且PriorityQueue会按照元素的自然顺序或者你自己定义的优先级顺序进行排序。

  PriorityQueue是一个无界队列,即队列的容量可以无限扩充。它是线程不安全的,不支持null元素。默认情况下,PriorityQueue是自然排序,也就是小根堆,也可以通过Comparator接口来指定元素的排序方式。

PriorityQueue的底层实现

  PriorityQueue是基于数组实现的,它的底层数据结构是一个小根堆。小根堆是一种完全二叉树,满足一个性质,即每个节点的值都小于或等于它的左右子节点的值。

  在PriorityQueue中,数组的第一个元素是堆顶,也就是优先级最高的元素。每次插入一个元素时,PriorityQueue会先将元素添加到数组末尾,然后通过上浮操作来维护小根堆的性质。每次删除堆顶元素时,PriorityQueue会先将数组末尾元素移动到堆顶,然后通过下沉操作来维护小根堆的性质。

源代码解析

PriorityQueue的构造函数

    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }

    public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

    public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) {
        this.comparator = comparator;
        this.queue = new Object[initialCapacity];
    }

在这里插入图片描述

  PriorityQueue有四个构造函数:默认构造函数、指定初始化容量的构造函数、指定Comparator的构造函数和同时指定初始化容量与Comparator的构造函数。

  当不指定初始化容量和Comparator时,将会使用默认值。默认容量为11,Comparator为null。

  如下是部分源码截图:

添加元素

    public boolean add(E e) {
        return offer(e);
    }

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

  添加元素时,会先判断队列是否已满,如果已满则通过grow()方法进行扩容。接着会将元素添加到数组末尾,然后通过siftUp()方法来维护小根堆的性质。

  如果指定了Comparator,则通过siftUpUsingComparator()方法来维护小根堆的性质;否则通过siftUpComparable()方法维护小根堆的性质。这里的siftUp()方法还是比较关键的,它是用来上浮元素,维护小根堆的性质的。

在这里插入图片描述

删除元素

    public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);
        return result;
    }

    private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }

  删除元素时,会先判断队列是否为空。如果不为空,就将堆顶元素取出作为返回值,然后将数组末尾的元素移动到堆顶,通过siftDown()方法来维护小根堆的性质。

  如果指定了Comparator,则通过siftDownUsingComparator()方法来维护小根堆的性质;否则通过siftDownComparable()方法维护小根堆的性质。

拓展:

  这段代码是Java中PriorityQueue类中的poll()方法的实现。poll()方法用于从队列中取出并删除队列头部的元素,如果队列为空则返回null。

  该方法首先检查队列是否为空,如果为空则返回null。否则,将队列中的元素个数减1,更新modCount属性表示这次操作改变了队列结构,将队列头部的元素用变量result存储。接着,将队列中最后一个元素用变量x存储,并将队列中最后一个元素置为null。若队列还有元素,调用siftDown()方法将变量x与队列中元素重新排序,确保队列满足小根堆的性质。最后,返回变量result,即队列中被删除的元素。

  在siftDown()方法中,首先判断comparator是否为null。如果不为null,则调用siftDownUsingComparator()方法,否则调用siftDownComparable()方法。这两个方法都是用来重建小根堆的,不同的是,siftDownUsingComparator()方法通过比较器来实现排序,而siftDownComparable()方法则通过元素的自然顺序来实现排序。

应用场景案例

任务调度

  假设我们需要实现一个任务调度器,能够按照任务的优先级来执行任务。我们可以将任务按照优先级添加到PriorityQueue中,然后按照队列中任务的顺序依次执行。

public class Task implements Comparable<Task> {

    private int priority;
    private Runnable runnable;

    public Task(int priority, Runnable runnable) {
        this.priority = priority;
        this.runnable = runnable;
    }

    public void run() {
        runnable.run();
    }

    @Override
    public int compareTo(Task o) {
        return Integer.compare(priority, o.priority);
    }

}

public class MyTaskScheduler {

    private PriorityQueue<Task> queue;

    public MyTaskScheduler() {
        queue = new PriorityQueue<>();
    }

    public void schedule(Task task) {
        queue.offer(task);
    }

    public void run() {
        while (!queue.isEmpty()) {
            Task task = queue.poll();
            task.run();
        }
    }

}

分析代码:

  这段代码定义了一个Task类和一个MyTaskScheduler类,用于实现任务调度。Task类包含了一个优先级和一个Runnable对象,用于存储待执行的任务和它的优先级。MyTaskScheduler类包含了一个优先队列,用于存储所有的任务,并且包括了两个方法:schedule()方法用于将任务加入到队列中,run()方法则用于执行队列中的所有任务。

  Task类实现了Comparable接口,重写了compareTo()方法,通过比较任务的优先级,来判断哪个任务先执行。MyTaskScheduler类使用了Java自带的PriorityQueue优先队列,保证了任务的执行顺序是按照优先级从高到低的顺序执行。在run()方法中,使用一个while循环,不断从队列中取出优先级最高的任务,直到队列为空。对于每个任务,调用它的run()方法来执行任务逻辑。

  这段代码可以用于实现多个任务的调度,通过设置不同的优先级,来控制不同任务的执行顺序。同时,使用优先队列可以保证任务按照优先级的顺序执行,提高了任务执行的效率。

网络代理

  假设我们需要实现一个网络代理,能够按照ip包的优先级来转发数据。我们可以将ip包按照优先级添加到PriorityQueue中,然后按照队列中ip包的顺序依次转发数据。

public class IpPacket implements Comparable<IpPacket> {

    private int priority;
    private byte[] data;

    public IpPacket(int priority, byte[] data) {
        this.priority = priority;
        this.data = data;
    }

    public byte[] getData() {
        return data;
    }

    @Override
    public int compareTo(IpPacket o) {
        return Integer.compare(priority, o.priority);
    }

}

public class MyNetworkProxy {

    private PriorityQueue<IpPacket> queue;

    public MyNetworkProxy() {
        queue = new PriorityQueue<>();
    }

    public void send(IpPacket packet) {
        queue.offer(packet);
    }

    public void receive() {
        while (!queue.isEmpty()) {
            IpPacket packet = queue.poll();
            // 转发数据
        }
    }

}

拓展:
  上面是一个简单的网络代理程序,其中包含两个类:IpPacketMyNetworkProxy

  IpPacket类表示一个IP数据包,包含数据的优先级和实际的数据。实现了Comparable接口,用于优先级的排序。

  MyNetworkProxy类表示一个网络代理,通过维护一个优先级队列来实现数据包的转发。send方法用于将数据包添加到队列中,receive方法用于从队列中取出优先级最高的数据包并进行转发。

  在MyNetworkProxy中,当队列不为空时,每次从队列头取出优先级最高的数据包进行转发,直到队列为空。

  这个程序中的优先级队列可以保证高优先级的数据包先被发送,以保证网络的效率和响应时间。

优缺点分析

优点

  • PriorityQueue是一个非常高效的数据结构,它的插入和删除元素的时间复杂度都是O(log n)。
  • PriorityQueue可以实现基于优先级的排序,适用于任务调度、事件处理等场景。
  • PriorityQueue在扩容时可以节省空间,只需将数组容量增加一半即可。
  • PriorityQueue支持自然排序和指定Comparator来定义元素的排序方式。

缺点

  • PriorityQueue是线程不安全的,不适合在多线程环境下使用。如果需要在多线程环境下使用,可以使用PriorityBlockingQueue。
  • PriorityQueue不支持随机访问元素,只能访问堆顶元素。如果需要随机访问元素,可以使用TreeSet。

类代码方法介绍

public

public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {

    /**
     * 序列化 ID
     */
    private static final long serialVersionUID = -7720805057305804111L;

    /**
     * 默认初始容量
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    /**
     * 底层数组,用于存储堆元素
     */
    transient Object[] queue;

    /**
     * 数组中元素的数量
     */
    private int size = 0;

    /**
     * 比较器,用于确定堆中元素的顺序
     */
    private final Comparator<? super E> comparator;

    /**
     * 修改次数,用于判断在迭代过程中堆是否发生了修改
     */
    transient int modCount = 0;

    /**
     * 构造一个初始容量为11的PriorityQueue,元素顺序按照自然顺序排列
     */
    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

    /**
     * 构造一个指定初始容量的PriorityQueue,元素顺序按照自然顺序排列
     */
    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }

    /**
     * 构造一个初始容量为11的PriorityQueue,元素顺序按照指定比较器排列
     */
    public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

    /**
     * 返回PriorityQueue的头部元素,如果队列为空,则返回null
     */
    public E peek() {
        if (size == 0) {
            return null;
        }
        return (E) queue[0];
    }

    /**
     * 返回PriorityQueue中元素的数量
     */
    public int size() {
        return size;
    }

    /**
     * 对元素进行排序,排序的规则由比较器决定
     */
    private void heapify() {
        for (int i = (size >>> 1) - 1; i >= 0; i--) {
            siftDown(i, (E) queue[i]);
        }
    }

    /**
     * 返回一个包含PriorityQueue中所有元素的数组
     */
    @Override
    public Object[] toArray() {
        return Arrays.copyOf(queue, size);
    }

  以上是Java中PriorityQueue类的部分源码。PriorityQueue是一个堆,可以存储任意类型的元素,但是需要这些元素是可比较的,可以按照一定的顺序进行排序。PriorityQueue实现了Queue接口,因此可以像队列一样进行添加和删除元素,并且堆的性质保证了每次返回的元素都是最优的。

  如下是部分源码截图:

在这里插入图片描述

具体分析如下:

  1. PriorityQueue类是一个泛型类,使用类名后面的<E>表示。

  2. 类中定义了一个序列化ID,一个底层数组用于存储堆元素,一个记录数组中元素数量的变量,一个记录堆发生修改次数的变量,以及一个比较器。其中比较器用于判断堆中元素的顺序。

  3. 类中定义了多个构造方法,可以创建一个初始容量为11的PriorityQueue,也可以指定初始容量和比较器。

  4. PriorityQueue类实现了Queue接口中的offer、peek和poll方法。其中offer方法用于将元素添加到PriorityQueue中,peek方法用于返回PriorityQueue的头部元素,如果队列为空,则返回null,poll方法用于删除PriorityQueue的头部元素,并返回该元素,如果队列为空,则返回null。

  5. 类中还定义了一个size方法,用于返回PriorityQueue中元素的数量。

  6. PriorityQueue类实现了Iterable接口,因此可以迭代PriorityQueue中的元素。在此基础上,类中定义了一个Itr迭代器类,用于遍历PriorityQueue中的元素。其中,由于堆不保证元素的顺序,因此元素的顺序是不确定的。

  7. 类中还实现了一个使用指定的Collection构造PriorityQueue的方法,用于将一个Collection中的元素添加到PriorityQueue中。

  8. heapify方法用于对元素进行排序,排序的规则由比较器决定。

  9. toArray方法用于返回一个包含PriorityQueue中所有元素的数组。其中,使用Arrays类的copyOf方法对底层数组进行复制和截取,以保证只返回PriorityQueue中的有效元素。

测试用例

  下面是一个简单的示例main函数,使用Java中的PriorityQueue实现一个整数优先级队列,并添加一些元素并打印结果:

测试代码演示

package com.demo.javase.day70;

import java.util.PriorityQueue;

/**
 * @Author bug菌
 * @Date 2023-11-06 16:08
 */
public class PriorityQueueTest {

    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(5);
        pq.add(1);
        pq.add(10);
        pq.add(3);
        pq.add(2);

        System.out.println("队列中的元素(从小到大):");
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }
    }
}

测试结果

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

输出结果:

队列中的元素(从小到大)1 2 3 5 10

  在这个示例中,我们创建了一个PriorityQueue对象pq,并添加了5个整数元素。然后,我们使用poll()方法按照优先级顺序逐个弹出元素,并打印结果。注意,PriorityQueue默认使用自然顺序(从小到大),因此我们不需要指定比较器。

实际执行结果如下:

在这里插入图片描述

测试代码分析

  根据如上测试用例,在此我给大家进行深入详细的解读一下测试代码,以便于更多的同学能够理解并加深印象。

  如上测试用例演示了Java中的PriorityQueue(优先队列)的用法。在主方法中,先创建了一个PriorityQueue对象pq,并向其中添加了五个整数元素(5,1,10,3,2)。然后通过while循环,从队列中取出元素并打印,因为PriorityQueue默认是小根堆,所以打印出来的元素是从小到大排列的。最终输出结果为:队列中的元素(从小到大):1 2 3 5 10

小结

  本文通过对Java中PriorityQueue的定义、特性、底层实现及源码解析进行详细分析,深入探讨了PriorityQueue的内部原理。PriorityQueue是一种基于数组实现的堆,它可以按照元素的优先级进行排序,常用于任务调度、事件处理等场景。PriorityQueue底层是一个小根堆,在元素添加和删除时,会通过上浮和下沉操作来维护小根堆的性质。同时,本文也介绍了PriorityQueue的应用场景案例以及优缺点分析,帮助读者更好地理解PriorityQueue。

  总之,PriorityQueue作为Java集合框架中的一个重要组成部分,对于Java开发者来说,是必不可少的知识点。读者可以通过学习本文,加深对PriorityQueue的理解,从而更好地应用于实际开发中。

总结

  本文从PriorityQueue的定义、特性和底层实现入手,深入剖析了Java中PriorityQueue的源码和应用场景案例,并对其进行了优缺点分析。PriorityQueue是一种非常高效的数据结构,可以实现基于优先级的排序,适用于任务调度、事件处理等场景。但是需要注意的是,它是线程不安全的,不支持随机访问元素。在使用PriorityQueue时,需要根据实际情况选择适合的数据结构和算法来解决问题。

  …
  好啦,这期的内容就基本接近尾声啦,若你想学习更多,可以参考这篇专栏总结《「滚雪球学Java」教程导航帖》,本专栏致力打造最硬核 Java 零基础系列学习内容,🚀打造全网精品硬核专栏,带你直线超车;欢迎大家订阅持续学习。

附录源码

  如上涉及所有源码均已上传同步在「Gitee」,提供给同学们一对一参考学习,辅助你更迅速的掌握。

☀️建议/推荐你


  无论你是计算机专业的学生,还是对编程有兴趣的小伙伴,都建议直接毫无顾忌的学习此专栏「滚雪球学Java」,bug菌郑重承诺,凡是学习此专栏的同学,均能获取到所需的知识和技能,全网最快速入门Java编程,就像滚雪球一样,越滚越大,指数级提升。

  最后,如果这篇文章对你有所帮助,帮忙给作者来个一键三连,关注、点赞、收藏,您的支持就是我坚持写作最大的动力。

  同时欢迎大家关注公众号:「猿圈奇妙屋」 ,以便学习更多同类型的技术文章,免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板、技术文章Markdown文档等海量资料。

📣关于我

  我是bug菌,CSDN | 掘金 | infoQ | 51CTO 等社区博客专家,历届博客之星Top30,掘金年度人气作者Top40,51CTO年度博主Top12,华为云 | 阿里云| 腾讯云等社区优质创作者,全网粉丝合计15w+ ;硬核微信公众号「猿圈奇妙屋」,欢迎你的加入!免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板等海量资料。


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。