目录
一、使用PriorityQueue的注意点
 二、PriorityQueue常用接口介绍
1. 优先级队列的构造
 2、PriorityQueue中对元素的比较
 3、插入/删除/获取优先级最高的元素
首页 Java java教程 Java集合框架之PriorityQueue优先级队列

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

Jun 09, 2022 am 11:47 AM
java

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

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

推荐学习:《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)

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

注意: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优先级队列的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

Java 中的平方根 Java 中的平方根 Aug 30, 2024 pm 04:26 PM

Java 中的平方根指南。下面我们分别通过例子和代码实现来讨论平方根在Java中的工作原理。

Java 中的完美数 Java 中的完美数 Aug 30, 2024 pm 04:28 PM

Java 完美数指南。这里我们讨论定义,如何在 Java 中检查完美数?,示例和代码实现。

Java 中的随机数生成器 Java 中的随机数生成器 Aug 30, 2024 pm 04:27 PM

Java 随机数生成器指南。在这里,我们通过示例讨论 Java 中的函数,并通过示例讨论两个不同的生成器。

Java 中的阿姆斯特朗数 Java 中的阿姆斯特朗数 Aug 30, 2024 pm 04:26 PM

Java 中的阿姆斯特朗数指南。这里我们讨论一下java中阿姆斯特朗数的介绍以及一些代码。

Java中的Weka Java中的Weka Aug 30, 2024 pm 04:28 PM

Java 版 Weka 指南。这里我们通过示例讨论简介、如何使用weka java、平台类型和优点。

Java 中的史密斯数 Java 中的史密斯数 Aug 30, 2024 pm 04:28 PM

Java 史密斯数指南。这里我们讨论定义,如何在Java中检查史密斯号?带有代码实现的示例。

Java Spring 面试题 Java Spring 面试题 Aug 30, 2024 pm 04:29 PM

在本文中,我们保留了最常被问到的 Java Spring 面试问题及其详细答案。这样你就可以顺利通过面试。

突破或从Java 8流返回? 突破或从Java 8流返回? Feb 07, 2025 pm 12:09 PM

Java 8引入了Stream API,提供了一种强大且表达力丰富的处理数据集合的方式。然而,使用Stream时,一个常见问题是:如何从forEach操作中中断或返回? 传统循环允许提前中断或返回,但Stream的forEach方法并不直接支持这种方式。本文将解释原因,并探讨在Stream处理系统中实现提前终止的替代方法。 延伸阅读: Java Stream API改进 理解Stream forEach forEach方法是一个终端操作,它对Stream中的每个元素执行一个操作。它的设计意图是处

See all articles