Java集合框架（PriorityQueue优先级队列讲解）

2023-04-25 88

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Java集合框架（PriorityQueue优先级队列讲解）

前言：

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中常见的几种构造方式，其他的大家可以参考帮助文档。

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);
    }
}