站长家园(原代码之家)(www.adminjie.com)网站源码,微信源码,游戏源码,商业源码分享平台。
当前位置:网站首页 技术文章 网络编程 正文

Java集合框架之PriorityQueue优先级队列

时间:2022-06-09 [网络编程]作者:fabuyuan 浏览:4 次

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

推荐学习:《java视频教程

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

priorityQueue在Java集合框架中的关系如下:

一、使用PriorityQueue的注意点

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

import java.util.PriorityQueue

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

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

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

5. 插入和删除元素的时间复杂度为log以2为底的n

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

7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素(想要变成大堆,需要我们重新比较方法、默认的比较方法是Comparable接口中的compareTo方法)

二、PriorityQueue常用接口介绍

1. 优先级队列的构造

此处只是列出了PriorityQueue中常见的几种构造方式,其他的大家可以参考帮助文档。

构造器功能介绍
PriorityQueue()创建一个空的优先级队列,默认容量是11
PriorityQueue(int
initialCapacity)
创建一个初始容量为initialCapacity的优先级队列,注意:initialCapacity不能小于1,否则会抛IllegalArgumentException异
PriorityQueue(Collection<?
extends E> c)
用一个集合来创建优先级队列
PriorityQueue(Comparator<? super E> comparator)创建具有默认初始容量的优先级队列,并根据指定的比较器对其元素进行比较
PriorityQueue(int initialCapacity, Comparator <? super E> comparator)

创建一个初始容量为initialCapacity的优先级队列,根据指定的比较器对其元素进行比较

注意:initialCapacity不能小于1,否则会抛IllegalArgumentException异

2、PriorityQueue中对元素的比较

看完了构造方法,我们重新来思考一个问题

优先级队列是如何实现有序的呢?因为优先级队列就是借助小根堆来实现的

在实现小根堆的过程我们知道这其中一定发生了元素的比较,所以PriorityQueue中的元素必须要能够比较大小,那么PriorityQueue是如何进行元素的比较呢?

PriorityQueue采用了:
Comparble和Comparator两种方式。

1. Comparble是默认的内部比较方式,如果用户插入自定义类型对象时,该类对象必须要实现Comparble接口,并覆写compareTo方法

2. 用户也可以选择使用比较器对象,如果用户插入自定义类型对象时,必须要提供一个比较器类,让该类实现Comparator接口并覆写compare方法。

我们看到这里程序报错了,为什么呢?因为我们插入的Child对象是不可比较的(即没有实现Comparable接口又没有采用自定义的比较器)

可以看到

即我们采用了默认的比较方法Comparable接口中的compareTo方法

此时我们再次看一下报错信息

看来是在往PriorityQueue中插入元素的时候出现了问题

那么我们打开PriorityQueue的源码看一下(下面是PriorityQueue中offer方法的源码)

再看看shiftUp的源码

继续点进去siftUpComparable

此时再回过头来看看我们放到PriorityQueue中的Child对象,他即没有自定义比较器又没有实现Comparable接口,当然报错呀!

那么好吧我们在Child类中实现Comparable接口,按年龄进行比较

import java.util.PriorityQueue;
class Child implements Comparable<Child>{
    int age;
    String name;

    public Child(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public int compareTo(Child o) {
        return this.age - o.age;  // 默认实现小根堆
    }

    @Override
    public String toString() {
        return "Child{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}
public class TestPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Child> priorityQueue = new PriorityQueue<>();

        priorityQueue.offer(new Child(12, "小亮"));
        priorityQueue.offer(new Child(11, "小红"));
        priorityQueue.offer(new Child(8, "小强"));
        System.out.println(priorityQueue);
    }
}

如果要实现大根堆,也好办

上面我们是实现了Compable接口,那么如果我们自定义一个年龄比较器呢?

class Child {
    int age;
    String name;

    public Child(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Child{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}
class AgeComparator implements Comparator<Child> {

    @Override
    public int compare(Child o1, Child o2) {
        return o1.age - o2.age; // 实现小根堆
        // return o2.ae - o1.age 实现大根堆
    }
}
public class TestPriorityQueue {
    public static void main(String[] args) {
        AgeComparator ageComparator = new AgeComparator();
        // 创建具有默认初始容量的 PriorityQueue ,并根据指定的比较器对其元素进行排序。
        PriorityQueue<Child> priorityQueue = new PriorityQueue<>(ageComparator);
        // 可以看到这里我的Child对象虽然没有实现Comparable接口,但因为我们对Child对象自定义了一个年龄比较器,所以插入元素不会报错
        priorityQueue.offer(new Child(12, "小亮"));
        priorityQueue.offer(new Child(11, "小红"));
        priorityQueue.offer(new Child(8, "小强"));
        System.out.println(priorityQueue);
    }
}

3、插入/删除/获取优先级最高的元素

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

boolean

isEmty()

检测优先级队列是否为空,为空返回true

推荐学习:《java视频教程》

以上就是Java集合框架之PriorityQueue优先级队列的详细内容,更多请关注站长家园其它相关文章!

本文标签:  java

转载请注明来源:Java集合框架之PriorityQueue优先级队列

本文永久链接地址:https://www.adminjie.com/post/13297.html

免责声明:
本站所发布的一切资源仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容。如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。

附:
二○○二年一月一日《计算机软件保护条例》第十七条规定:为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬!鉴于此,也希望大家按此说明研究软件!

版权声明:
一、本站致力于为软件爱好者提供国内外软件开发技术和软件共享,着力为用户提供优资资源。
二、本站提供的部分源码下载文件为网络共享资源,请于下载后的24小时内删除。如需体验更多乐趣,还请支持正版。
三、我站提供用户下载的所有内容均转自互联网。如有内容侵犯您的版权或其他利益的,若有侵犯你的权益请:提交版权证明文件到邮箱 2225329873#qq.com(#换为@) 站长会进行审查之后,情况属实的会在三个工作日内为您删除。

  • 站长家园(原代码之家)会员升级
  • 最新文章
    • Redis集群操作实例详解

      Redis集群操作实例详解

      本篇文章给大家带来了关于Redis的相关知识,其中主要整理了集群操作的相关问题,包括了增加redis实例、配置8007为主节点、配置8008为8007的从节点等...

    • MySQL日志管理(总结分享)

      MySQL日志管理(总结分享)

      本篇文章给大家带来了关于mysql的相关知识,其中主要整理了日志管理的相关问题,包括了错误日志、通用查询日志、二进制日志等等内容,下面一起来看一下,希望对大家有...

    • html5草案是哪一年发布的

      html5草案是哪一年发布的

      html5草案是在2008年发布的。HTML5草案的前身是“WebApplications1.0”,是在2004年被“WHATWG”提出,直到2008年1月...

    • Vue3和Vue2的差异是什么?全方位对比一下!

      Vue3和Vue2的差异是什么?全方位对比一下!

      Vue3和Vue2的差异是什么?下面本篇文章给大家全方位对比Vue3与Vue2,聊聊Vue3与Vue2的区别,希望对大家有所帮助!从Vue3发布以来,我就一直对...

    • 浮动是css3的新特性吗

      浮动是css3的新特性吗

      浮动不是css3的新特性。定义元素在哪个方向浮动的float属性在css1时就已经可以使用了,css的浮动会使元素向左或向右移动,其周围的元素也会重新排列,一个...

    热门文章