首页 > 编程语言 >Java中的优先级队列(PriorityQueue)(如果想知道Java中有关优先级队列的知识点,那么只看这一篇就足够了!)

Java中的优先级队列(PriorityQueue)(如果想知道Java中有关优先级队列的知识点,那么只看这一篇就足够了!)

时间:2024-07-24 12:59:38浏览次数:20  
标签:优先级 队列 元素 elem PriorityQueue int Java

        前言:优先级队列(Priority Queue)是一种抽象数据类型,其中每个元素都关联有一个优先级,元素按照优先级顺序进行处理。


✨✨✨这里是秋刀鱼不做梦的BLOG

✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客

先让我们看一下本文大致的讲解内容:

目录

1.优先队列的初识

        (1)优先级队列的定义

        (2)PriorityQueue的特性

2.优先级队列的模拟实现

3.优先级队列中常用API

        (1)创建优先级队列

        (2)插入/删除/获取优先级最高的元素/获取个数/清空/判断是否为空

4.优先级队列的使用

1. 任务调度

2. 事件驱动模拟

3. 图算法

4. 数据流处理


1.优先队列的初识

        (1)优先级队列的定义

        在开始学习Java中优先级队列的使用之前,先让我们了解一下什么是Java中的优先级队列(PriorityQueue):

        优先级队列(Priority Queue)是一种抽象数据类型,其中每个元素都关联有一个优先级,元素按照优先级顺序进行处理。与标准队列不同,优先级队列中的元素处理顺序并非按插入顺序,而是按照优先级高低来决定。

        如果读者看了优先级队列的定义之后还是不是太理解什么是优先级队列,那么现在我们使用一个日常生活中的例子来帮助你理解:

        ——例如在医院急诊室,虽然你可能先到,但是医生会根据病人的病情严重程度来决定治疗顺序。病情严重的病人(例如,心脏病发作的病人)会被优先治疗,而病情较轻的病人(例如,轻微的感冒)会被安排在后面。

        这样我相信读者就对优先级队列有了初步的认识了!!!

        (2)PriorityQueue的特性

        Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队,而对于PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,而本文我们主要介绍是PriorityQueue。

其在Java集合框架中的关系图为:

关于PriorityQueue的使用要注意:

        1. 使用时必须导入PriorityQueue所在的包,即:

import java.util.PriorityQueue;

        2. PriorityQueue中放置的元素必须要能够比较大小,不能插入无法比较大小的对象,否则会抛出ClassCastException异常;

        3. 不能插入null对象,否则会抛出NullPointerException;

        4. 没有容量限制,可以插入任意多个元素,其内部可以自动扩容;

        5. 插入和删除元素的时间复杂度为O(logN);

        6. PriorityQueue底层使用了堆数据结构;

        7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素;

        至此,我们通过上述对Java中的优先级队列的简单讲述,我们就大致的了解了什么是Java中的优先级队列了!

2.优先级队列的模拟实现

        在了解完了什么是Java中的优先级队列之后,现在让我们想想看如何去自我实现一个Java中的优先级队列呢?

——这里我们已经在每处加上了注释,希望读者可以跟随着注释进行理解代码:

package Demo1;

import java.util.Arrays;

// 堆的自我实现 - 创建堆 + 插入数据 + 删除数据 + 返回堆顶元素 + 判断是否为空
public class MyPriorityQueue {
    public int[] elem; // 存储堆元素的数组
    public int useSize; // 当前堆中元素的个数

    // 初始化堆
    public MyPriorityQueue(int[] array) {
        elem = new int[11]; // 初始化堆的容量
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i]; // 将传入的数组元素放入堆中
            useSize++; // 更新堆中元素的个数
        }
        makeBigHeap(array, useSize); // 创建大根堆
    }

    // 整体创建堆
    public void makeBigHeap(int[] array, int useSize) {
        // 从最后一个非叶子节点开始向上调整
        for (int parent = (useSize - 1 - 1) / 2; parent >= 0; parent--) {
            shiftDown(parent, useSize); // 对每个非叶子节点进行下沉操作
        }
    }

    // 下沉操作
    private void shiftDown(int root, int useSize) {
        int child = 2 * root + 1; // 左子节点索引
        while (child < useSize) { // 遍历堆
            // 如果右子节点存在且右子节点的值大于左子节点的值,选择右子节点
            if (child + 1 < useSize && elem[child] < elem[child + 1]) {
                child++;
            }
            // 如果当前节点的值小于子节点的值,交换它们
            if (elem[root] < elem[child]) {
                swap(root, child);
                root = child; // 更新根节点为被交换的子节点
                child = 2 * root + 1; // 更新左子节点的索引
            } else {
                break; // 如果根节点的值不小于任何子节点,退出循环
            }
        }
    }

    // 在堆中插入元素
    private boolean isFull() {
        return useSize == elem.length; // 判断堆是否满了
    }

    public void offer(int val) {
        if (isFull()) {
            elem = Arrays.copyOf(elem, 2 * elem.length); // 扩容
        }
        elem[useSize] = val; // 将新元素放入堆的末尾
        shiftUp(useSize); // 上浮操作调整堆
        useSize++; // 更新堆中元素的个数
    }

    // 上浮操作
    private void shiftUp(int child) {
        int parent = (child - 1) / 2; // 计算父节点的索引
        while (parent >= 0) {
            // 如果当前节点的值大于父节点的值,交换它们
            if (elem[parent] < elem[child]) {
                swap(parent, child);
                child = parent; // 更新子节点为被交换的父节点
                parent = (child - 1) / 2; // 更新父节点的索引
            } else {
                break; // 如果当前节点的值不大于父节点的值,退出循环
            }
        }
    }

    // 删除堆中元素
    public void poll() {
        if (isEmpty()) {
            throw new RuntimeException("堆中元素为空!"); // 如果堆为空,抛出异常
        }
        swap(0, useSize - 1); // 将堆顶元素与最后一个元素交换
        useSize--; // 更新堆中元素的个数
        shiftDown(0, useSize); // 对堆顶元素进行下沉操作
    }

    // 获取堆顶元素
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("堆中元素为空!"); // 如果堆为空,抛出异常
        }
        return elem[0]; // 返回堆顶元素
    }

    // 判断堆是否为空
    private boolean isEmpty() {
        return useSize == 0; // 如果堆中没有元素,返回 true
    }

    // 交换数组中的两个元素
    private void swap(int pos1, int pos2) {
        int temp = elem[pos1];
        elem[pos1] = elem[pos2];
        elem[pos2] = temp;
    }
}
public class Test {
    public static void main(String[] args) {
        // 初始化一个整数数组
        int[] array = {1, 4, 2, 7, 9, 10, 5, 6, 8, 3};
        
        // 创建一个优先级队列实例
        MyPriorityQueue myPriorityQueue = new MyPriorityQueue(array);
        
        // 向优先级队列中插入多个元素
        myPriorityQueue.offer(5);
        myPriorityQueue.offer(3);
        myPriorityQueue.offer(8);
        myPriorityQueue.offer(1);

        // 打印堆顶元素
        System.out.println(myPriorityQueue.peek());

        // 删除堆顶元素
        myPriorityQueue.poll();
        
        // 判断堆是否为空,并打印结果(注意这里原代码并未打印结果,需手动添加打印语句)
        System.out.println("堆是否为空: " + myPriorityQueue.isEmpty());
    }
}
public class Test {
    public static void main(String[] args) {
        // 初始化一个整数数组
        int[] array = {1, 4, 2, 7, 9, 10, 5, 6, 8, 3};
        
        // 创建一个优先级队列实例
        MyPriorityQueue myPriorityQueue = new MyPriorityQueue(array);
        
        // 向优先级队列中插入多个元素
        myPriorityQueue.offer(5);
        myPriorityQueue.offer(3);
        myPriorityQueue.offer(8);
        myPriorityQueue.offer(1);

        // 打印堆顶元素
        System.out.println(myPriorityQueue.peek());

        // 删除堆顶元素
        myPriorityQueue.poll();
        
        // 判断堆是否为空,并打印结果(注意这里原代码并未打印结果,需手动添加打印语句)
        System.out.println("堆是否为空: " + myPriorityQueue.isEmpty());
    }
}

        从中我们可以看到我们使用堆这个数据结果来自我实现了从 - 创建堆 - 插入数据 - 删除数据 - 返回堆顶元素 - 判断是否为空等优先队列中的操作。至此我们完成了自我实现Java中的优先级队列(PriorityQueue)。

如果对于堆这种数据结构不了解的读者,可以阅读---------->Java中的Heap(堆)(如果想知道Java中有关堆的知识点,那么只看这一篇就足够了!)-CSDN博客

3.优先级队列中常用API

        通过上面的学习,我们已经了解了什么是Java中的优先级队列,并且自我实现了优先级队列,现在让我们看看Java中内置的优先级队列该如何使用吧!

        (1)创建优先级队列

PriorityQueue类提供了多种构造方法,允许创建不同配置的优先级队列。

构造器功能
PriorityQueue()创建一个空的优先级队列,默认容量是11
PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列,注意:
initialCapacity不能小于1,否则IllegalArgumentException异常
PriorityQueue(Collection<? extends E> c)

用一个集合来创建优先级队列

例子:

import java.util.PriorityQueue;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        // 默认初始容量的优先级队列
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        // 指定初始容量的优先级队列
        PriorityQueue<Integer> pqWithCapacity = new PriorityQueue<>(20);
        
        // 使用比较器的优先级队列
        PriorityQueue<Integer> pqWithComparator = new PriorityQueue<>(new CustomComparator());
    }
}

        ——这样我们就会常见Java中的优先级队列了!

在了解了如何创建一个优先级队列之后,接下来让我们看一下如何去操作这个创建的优先级队列。

        (2)插入/删除/获取优先级最高的元素/获取个数/清空/判断是否为空

函数名功能
boolean offer(E e)插入元素e,插入成功返回true,如果e对象为空,抛出NullPointerException异常,时间复杂度O(logN),注意:空间不够时候会进行扩容
E peek()获取优先级最高的元素,如果优先级队列为空,返回null
E poll()移除优先级最高的元素并返回,如果优先级队列为空,返回null
int size()获取有效元素的个数
void clear()清空
boolean isEmpty()检测优先级队列是否为空,空返回true

例子:

import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        // 初始化一个整数数组
        int[] arr = {4, 1, 9, 2, 8, 0, 7, 3, 6, 5};

        PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
        
        // 将数组中的元素添加到优先级队列中
        for (int e : arr) {
            q.offer(e);
        }
        
        // 打印优先级队列中有效元素的个数
        System.out.println(q.size());
        
        // 获取并打印优先级队列中优先级最高的元素(即最小值,因为是最小堆)
        System.out.println(q.peek());
        
        // 从优先级队列中删除两个元素
        q.poll();
        q.poll();
        
        // 打印删除两个元素后,优先级队列中有效元素的个数
        System.out.println(q.size());
        
        // 获取并打印当前优先级最高的元素
        System.out.println(q.peek());
        
        // 向优先级队列中插入一个新的元素
        q.offer(0);
        
        // 获取并打印插入新元素后的优先级最高的元素
        System.out.println(q.peek());
        
        // 清空优先级队列中的所有有效元素
        q.clear();
        
        // 检测优先级队列是否为空,并打印结果
        if (q.isEmpty()) {
            System.out.println("优先级队列已经为空!!!");
        } else {
            System.out.println("优先级队列不为空");
        }
    }
}

        ——这样我们就大致的了解了如何操作Java中的优先级队列了!!!

4.优先级队列的使用

        优先级队列(Priority Queue)是一种特殊的数据结构,用于处理具有优先级的元素。它的主要特点是能够高效地插入元素并以优先级顺序访问和删除元素。以下是优先级队列的一些主要应用场景:

1. 任务调度

  • 场景: 操作系统和调度系统常常需要管理多个任务,每个任务具有不同的优先级。

  • 用法: 优先级队列可以用来实现任务调度系统,其中优先级高的任务会被优先执行。比如,操作系统的进程调度器会使用优先级队列来决定哪个进程应该优先获得 CPU 时间。

2. 事件驱动模拟

  • 场景: 在模拟系统(如网络仿真或离散事件模拟)中,事件会在未来的某个时间点发生。

  • 用法: 优先级队列用于存储和处理这些事件,确保在模拟中按事件的发生时间顺序处理它们。

3. 图算法

  • 场景: 在计算图的最短路径(如 Dijkstra 算法)或最小生成树(如 Prim 算法)时,需要按边的权重或节点的距离进行操作。

  • 用法: 使用优先级队列可以有效地管理和访问图中的边或节点,以支持这些算法的高效执行。

4. 数据流处理

  • 场景: 数据流中的数据可能具有不同的重要性或优先级。

  • 用法: 在处理实时数据流时,优先级队列可以用来根据数据的优先级顺序处理数据。

这样我们就大致的了解了Java中的优先级队列在日常中的使用地方了!


以上就是本篇文章的全部内容了~~~

标签:优先级,队列,元素,elem,PriorityQueue,int,Java
From: https://blog.csdn.net/2302_80198073/article/details/140657302

相关文章

  • 基于Java+SpringBoot+Vue的卓越导师双选系统的设计与开发(源码+lw+部署文档+讲解等)
    文章目录前言项目背景介绍技术栈后端框架SpringBoot前端框架Vue数据库MySQL(MyStructuredQueryLanguage)具体实现截图详细视频演示系统测试系统测试目的系统功能测试系统测试结论代码参考数据库参考源码获取前言......
  • java内部类详解
    24-07-22java内部类目录24-07-22java内部类什么是内部类内部类的分类局部内部类匿名内部类AnonymousClass(重点)成员内部类静态内部类什么是内部类简单来说,一个类的内部嵌套了另一个类结构,被嵌套的结构被称为内部类,嵌套其他类的类我们称为外部类。在开始学习之前,我们先来回想......
  • 【数据结构】队列详解和模拟实现
    大家好,今天我们学习队列,本篇博客主要涉及一般队列,环形队列和双端队列,每个队列应用场景均有所差异,下面我们一起来看看吧。队列(Queue)一,概念队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出的特性入队列:进行插入操作的一端称为队尾(Ta......
  • Druid出现DruidDataSource - recyle error - recyle error java.lang.InterruptedExce
    原文链接: https://www.cnblogs.com/zhoading/p/14040939.htmlhttps://www.cnblogs.com/lingyejun/p/9064114.html 一、问题回顾线上的代码之前运行的都很平稳,突然就出现了一个很奇怪的问题,看错误信息是第三方框架Druid报出来了,连接池回收连接时出现的问题。1234......
  • Java面试题总结(持续更新)
    1、this关键字和super关键字的区别及联系this关键字用在本类中。在类的内部,可以在任何方法中使用this引用当前对象。this关键字是用来解决全局变量和局部变量之间的冲突。this()可以调用同类中重载的构造方法,并且需要放在第一行。super关键字用在子类中。在子类中可以通......
  • 在 Kubernetes 中设置 Pod 优先级及其调度策略详解
    个人名片......
  • JavaScript中的new map()和new set()使用详细(new map()和new set()的区别)
    简介:newMap():在JavaScript中,newMap()用于创建一个新的Map对象。Map对象是一种键值对的集合,其中的键是唯一的,值可以重复。newSet():在JavaScript中,newSet()是用来创建一个新的Set对象的语法。Set对象是一种集合,其中的值是唯一的,没有重复的值。newSet()可以用......
  • Aspose项目实战!pdf、cells for java
    Aspose实战使用:Excel与PDF转换工具类在这篇博客中,我将分享如何使用Aspose库来实现Excel文件与PDF文件之间的转换。我会重点分析一个工具类AsposeOfficeUtil,这个类封装了多个与Excel和PDF相关的操作方法,帮助开发者高效地进行文件转换和数据处理。此外,还将提......
  • JAVA 打印菱形的程序(Program to print the Diamond Shape)
    给定一个数字n,编写一个程序来打印一个有2n行的菱形。例子://JAVACodetoprint //thediamondshapeimportjava.util.*;classGFG{     //Printsdiamondpattern  //with2nrows  staticvoidprintDiamond(intn)  {    i......
  • 基于Java+SpringBoot+Vue的精品在线试题库系统的设计与开发(源码+lw+部署文档+讲解等)
    文章目录前言项目背景介绍技术栈后端框架SpringBoot前端框架Vue数据库MySQL(MyStructuredQueryLanguage)具体实现截图详细视频演示系统测试系统测试目的系统功能测试系统测试结论代码参考数据库参考源码获取前言......