深入理解PriorityQueue的特性

文章目录

• 一、PriorityQueue的特性
• 二、 PriorityQueue的构造方法。
• • 无参构造
  • 指定容量
  • 传入比较器
  • 那如何建立一个大根堆呢？
• 三、 PriorityQueue常用操作

一、PriorityQueue的特性

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的

使用操作：

1.在我们使用优先级队列时，必须导入相应的包

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

让我们深入了解一下这个问题。

class Person {
    int age;
    String name;

    public Person(int age, String name) {
        this.age = age;
        this.name = name;
    }
}
public class Test {
    public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.offer(new Person(18,"张三"));
    }
}

我们试着只插入一个元素，发现并没有报错。

public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.offer(new Person(18,"张三"));
        priorityQueue.offer(new Person(20,"李四"));
    }

我们发现当我们插入第二个元素的时候，系统报了类转换异常，那是为什么呢？我们上升到源码的层次上去分析一下。

当我们只传入一个参数时，系统默认调用两个参数的构造方法。

第一个参数是一个静态常量，默认为11.

指定此队列容量为11，comparator为null。

直到这里构造方法就完成了，接下来我们再看一下系统的offer方法。

我们可以发现，当我们传入第一个元素时，它直接赋值，没有进行其他操作，这也是我们为什么刚在插入第一个元素时没有报错的原因。

我们再来看插入不为第一个元素时是什么情况，这里我们的comparator为null,所以进入第二个方法。

我们发现当插入时，会将我们传入的元素强制转换为Comparable接口,但是我我们的类并没有实现这个接口，所以会报类转换异常。

所以我们想插入多个元素时，对应的类比较实现相应的接口和方法。

class Person implements Comparable{
    int age;
    String name;

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

    @Override
    public int compareTo(Person o) {
        return this.age - o.age;
    }
}
public class Test {
    public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.offer(new Person(20,"李四"));
        priorityQueue.offer(new Person(18,"张三"));
        System.out.println("=============================");
    }
}

这样就可以正常操作了。

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

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

我们可以发现，每次插入的时候，系统都会判断一个这个优先级队列是否为满，如果满了就grow。

当你的优先级队列容量小于64时，进行2倍+2扩容，如果大于64时，进行1.5倍扩容。

对扩容后的大小进行判断，当大于2147483639时，就会重新计算。

如果传入的容量大小大于2147483639时，赋值为2147483647，否则赋值为2147483639。

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

上一篇文章我们深入讲过元素的插入和删除的时间复杂度。

6. PriorityQueue底层使用了堆数据结构, (注意：此处大家可以不用管什么是堆，后文中有介绍)

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

是我们在向上操作时的判断条件，在后面我们想建大根堆时，也会灵活变通。

二、 PriorityQueue的构造方法。

无参构造

创建一个空的优先级队列，默认容量是11，上面我们具体讲过，这里就不在一一阐述。

指定容量

PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列，注意：initialCapacity不能小于1，否则会抛IllegalArgumentException异常

传入比较器

public PriorityQueue(int initialCapacity, Comparator comparator)

当我们传入指定的比较器之后，我们就可以按照指定比较方式进行插入比较，先来举一个简单的例子。

class Student{
    String name;
    int age;

    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
}
class ageComparator implements Comparator {
    @Override
    public int compare(Student o1, Student o2) {
        return o1.age - o2.age;
    }
}
    public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue(2,new ageComparator());
        priorityQueue.offer(new Student("李四",20));
        priorityQueue.offer(new Student("张三",18));
        System.out.println("---------------");
    }

在这里我们实现一个比较器，然后传入，可以正常操作。

这样单独写一个类太麻烦了，有没有简单一点的操作。

public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue(2, new Comparator() {
            @Override
            public int compare(Student o1, Student o2) {
                return o1.age - o2.age;
            }
        });
        priorityQueue.offer(new Student("李四",20));
        priorityQueue.offer(new Student("张三",18));
        System.out.println("---------------");
    }

这里我们使用了一下匿名内部类来实现比较器。

那如何建立一个大根堆呢？

我们分析源码时，我们发现这里决定着向上操作的判断决定着我们建立的是大根堆还是小根堆。我们只需要在传入比较器中的条件即可。

public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue(2, new Comparator() {
            @Override
            public int compare(Student o1, Student o2) {
                return o2.age - o1.age;
            }
        });
        priorityQueue.offer(new Student("李四",20));
        priorityQueue.offer(new Student("张三",18));
        System.out.println("---------------");
    }

这样就成功创建了一个大根堆了。

三、 PriorityQueue常用操作