深入理解PriorityQueue的特性

淩亂°似流年 2023-09-27 11:58 101阅读 0赞

![在这里插入图片描述][7912ce5c7c9746e280297b6668b68289.gif_pic_center]

#### 文章目录 ####

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

## 一、PriorityQueue的特性 ##

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的  
![在这里插入图片描述][4e64fea8e8ca469fb79d1ea6c6987604.png]  
**使用操作：**  
**1.在我们使用优先级队列时，必须导入相应的包**  
![在这里插入图片描述][3506643fa5fc404fa25eb78f5d847a46.png]  
**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<Person> priorityQueue = new PriorityQueue<>();
            priorityQueue.offer(new Person(18,"张三"));
        }
    }

我们试着只插入一个元素，发现并没有报错。  
![在这里插入图片描述][52f68d8fee384c718d47953b158fb541.png]

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

![在这里插入图片描述][57835a76417349f38d9dd3f135fce42b.png]  
我们发现当我们插入第二个元素的时候，系统报了类转换异常，那是为什么呢？我们上升到源码的层次上去分析一下。  
![在这里插入图片描述][0369972ec6c544dd9c5933e495c9d95c.png]  
当我们只传入一个参数时，系统默认调用两个参数的构造方法。  
![在这里插入图片描述][719194abf6cf4f208a11a27a8e023240.png]  
第一个参数是一个静态常量，默认为11.  
![在这里插入图片描述][69075ae84e5b4d81b2d65a37add89f72.png]  
指定此队列容量为11，comparator为null。  
![在这里插入图片描述][7a18821a9a1b4512a2ffa5f72a7031b1.png]  
直到这里构造方法就完成了，接下来我们再看一下系统的offer方法。  
![在这里插入图片描述][58bde421771f4b40a89ba30d7804337c.png]  
我们可以发现，当我们传入第一个元素时，它直接赋值，没有进行其他操作，这也是我们为什么刚在插入第一个元素时没有报错的原因。  
![在这里插入图片描述][d929fa5727d3405a938b007bf9211af9.png]  
我们再来看插入不为第一个元素时是什么情况，这里我们的comparator为null,所以进入第二个方法。  
![在这里插入图片描述][039a0f15ad434fa891e25f8ea1019b78.png]  
我们发现当插入时，会将我们传入的元素强制转换为Comparable接口,但是我我们的类并没有实现这个接口，所以会报类转换异常。  
所以我们想插入多个元素时，对应的类比较实现相应的接口和方法。

class Person implements Comparable<Person>{
        
        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<Person> priorityQueue = new PriorityQueue<>();
            priorityQueue.offer(new Person(20,"李四"));
            priorityQueue.offer(new Person(18,"张三"));
            System.out.println("=============================");
        }
    }

![在这里插入图片描述][40cbd90d42454aceb0943937120b8545.png]  
这样就可以正常操作了。

**3. 不能插入null对象，否则会抛出NullPointerException**  
![在这里插入图片描述][6a478d7cac2840e7a5975a2203235d75.png]  
**4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容**  
![在这里插入图片描述][4a2af8730d484c5185fccb4542a25257.png]  
我们可以发现，每次插入的时候，系统都会判断一个这个优先级队列是否为满，如果满了就grow。  
![在这里插入图片描述][1534ec06168f47028ad4ebd93e1b4621.png]  
当你的优先级队列容量小于64时，进行2倍+2扩容，如果大于64时，进行1.5倍扩容。  
![在这里插入图片描述][8bcdbbe12035419189d13bc478643ed3.png]  
对扩容后的大小进行判断，当大于2147483639时，就会重新计算。![在这里插入图片描述][760f3556d0b94f389b07444db5474016.png]  
![在这里插入图片描述][f79d85d3393444318825c62f8423f0fe.png]  
如果传入的容量大小大于2147483639时，赋值为2147483647，否则赋值为2147483639。

**5. 插入和删除元素的时间复杂度为O(logn)**  
上一篇文章我们深入讲过元素的插入和删除的时间复杂度。

**6. PriorityQueue底层使用了堆数据结构, (注意：此处大家可以不用管什么是堆，后文中有介绍)**  
**7. PriorityQueue默认情况下是小堆—即每次获取到的元素都是最小的元素**  
![在这里插入图片描述][87cda9786a854091aebcf3934913a142.png]  
是我们在向上操作时的判断条件，在后面我们想建大根堆时，也会灵活变通。

## 二、 PriorityQueue的构造方法。 ##

### 无参构造 ###

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

### 指定容量 ###

PriorityQueue(int initialCapacity)创建一个初始容量为initialCapacity的优先级队列，注意：initialCapacity不能小于1，否则会抛IllegalArgumentException异常  
![在这里插入图片描述][14bdb0b1940f42649d2b576e4b2ec16e.png]  
![在这里插入图片描述][bcd6f3eb8dd342acb4511e19a31ed51d.png]

### 传入比较器 ###

public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)  
![在这里插入图片描述][662d29eaf6f14a24ab5a6c1a036ca71b.png]  
当我们传入指定的比较器之后，我们就可以按照指定比较方式进行插入比较，先来举一个简单的例子。

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

在这里我们实现一个比较器，然后传入，可以正常操作。  
![在这里插入图片描述][2da1cf0fce404dcfa721afd50576ae89.png]  
这样单独写一个类太麻烦了，有没有简单一点的操作。

public static void main(String[] args) {
        
            PriorityQueue<Student> priorityQueue = new PriorityQueue<>(2, new Comparator<Student>() {
        
                @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("---------------");
        }

这里我们使用了一下匿名内部类来实现比较器。  
![在这里插入图片描述][b32f96ea8a5940779a5ed7db42cba2be.png]

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

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

public static void main(String[] args) {
        
            PriorityQueue<Student> priorityQueue = new PriorityQueue<>(2, new Comparator<Student>() {
        
                @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("---------------");
        }

![在这里插入图片描述][2694b8113ff9401994a4ee0288eb4e46.png]  
![在这里插入图片描述][6616d1388a9e46e09c07339f0f5e50a2.png]  
这样就成功创建了一个大根堆了。

## 三、 PriorityQueue常用操作 ##

<table> 
 <thead> 
  <tr> 
   <th>函数名</th> 
   <th>功能介绍</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>offer(E e)</td> 
   <td>插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时间复杂度 ，注意：空间不够时候会进行扩容</td> 
  </tr> 
  <tr> 
   <td>E peek()</td> 
   <td>获取优先级最高的元素，如果优先级队列为空，返回null</td> 
  </tr> 
  <tr> 
   <td>E poll()</td> 
   <td>移除优先级最高的元素并返回，如果优先级队列为空，返回null</td> 
  </tr> 
  <tr> 
   <td>int size()</td> 
   <td>获取有效元素的个数</td> 
  </tr> 
  <tr> 
   <td>void clear()</td> 
   <td>清空</td> 
  </tr> 
  <tr> 
   <td>boolean isEmpty()</td> 
   <td>检测优先级队列是否为空，空返回true</td> 
  </tr> 
  <tr> 
   <td>上一篇中我们已经一一实现，在这里我们就不再进行操作了。</td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

[7912ce5c7c9746e280297b6668b68289.gif_pic_center]: https://img-blog.csdnimg.cn/7912ce5c7c9746e280297b6668b68289.gif#pic_center
[4e64fea8e8ca469fb79d1ea6c6987604.png]: https://img-blog.csdnimg.cn/4e64fea8e8ca469fb79d1ea6c6987604.png
[3506643fa5fc404fa25eb78f5d847a46.png]: https://img-blog.csdnimg.cn/3506643fa5fc404fa25eb78f5d847a46.png
[52f68d8fee384c718d47953b158fb541.png]: https://img-blog.csdnimg.cn/52f68d8fee384c718d47953b158fb541.png
[57835a76417349f38d9dd3f135fce42b.png]: https://img-blog.csdnimg.cn/57835a76417349f38d9dd3f135fce42b.png
[0369972ec6c544dd9c5933e495c9d95c.png]: https://img-blog.csdnimg.cn/0369972ec6c544dd9c5933e495c9d95c.png
[719194abf6cf4f208a11a27a8e023240.png]: https://img-blog.csdnimg.cn/719194abf6cf4f208a11a27a8e023240.png
[69075ae84e5b4d81b2d65a37add89f72.png]: https://img-blog.csdnimg.cn/69075ae84e5b4d81b2d65a37add89f72.png
[7a18821a9a1b4512a2ffa5f72a7031b1.png]: https://img-blog.csdnimg.cn/7a18821a9a1b4512a2ffa5f72a7031b1.png
[58bde421771f4b40a89ba30d7804337c.png]: https://img-blog.csdnimg.cn/58bde421771f4b40a89ba30d7804337c.png
[d929fa5727d3405a938b007bf9211af9.png]: https://img-blog.csdnimg.cn/d929fa5727d3405a938b007bf9211af9.png
[039a0f15ad434fa891e25f8ea1019b78.png]: https://img-blog.csdnimg.cn/039a0f15ad434fa891e25f8ea1019b78.png
[40cbd90d42454aceb0943937120b8545.png]: https://img-blog.csdnimg.cn/40cbd90d42454aceb0943937120b8545.png
[6a478d7cac2840e7a5975a2203235d75.png]: https://img-blog.csdnimg.cn/6a478d7cac2840e7a5975a2203235d75.png
[4a2af8730d484c5185fccb4542a25257.png]: https://img-blog.csdnimg.cn/4a2af8730d484c5185fccb4542a25257.png
[1534ec06168f47028ad4ebd93e1b4621.png]: https://img-blog.csdnimg.cn/1534ec06168f47028ad4ebd93e1b4621.png
[8bcdbbe12035419189d13bc478643ed3.png]: https://img-blog.csdnimg.cn/8bcdbbe12035419189d13bc478643ed3.png
[760f3556d0b94f389b07444db5474016.png]: https://img-blog.csdnimg.cn/760f3556d0b94f389b07444db5474016.png
[f79d85d3393444318825c62f8423f0fe.png]: https://img-blog.csdnimg.cn/f79d85d3393444318825c62f8423f0fe.png
[87cda9786a854091aebcf3934913a142.png]: https://img-blog.csdnimg.cn/87cda9786a854091aebcf3934913a142.png
[14bdb0b1940f42649d2b576e4b2ec16e.png]: https://img-blog.csdnimg.cn/14bdb0b1940f42649d2b576e4b2ec16e.png
[bcd6f3eb8dd342acb4511e19a31ed51d.png]: https://img-blog.csdnimg.cn/bcd6f3eb8dd342acb4511e19a31ed51d.png
[662d29eaf6f14a24ab5a6c1a036ca71b.png]: https://img-blog.csdnimg.cn/662d29eaf6f14a24ab5a6c1a036ca71b.png
[2da1cf0fce404dcfa721afd50576ae89.png]: https://img-blog.csdnimg.cn/2da1cf0fce404dcfa721afd50576ae89.png
[b32f96ea8a5940779a5ed7db42cba2be.png]: https://img-blog.csdnimg.cn/b32f96ea8a5940779a5ed7db42cba2be.png
[79a72f6bf0e047deb34bf2ead6b11cea.png]: https://img-blog.csdnimg.cn/79a72f6bf0e047deb34bf2ead6b11cea.png
[2694b8113ff9401994a4ee0288eb4e46.png]: https://img-blog.csdnimg.cn/2694b8113ff9401994a4ee0288eb4e46.png
[6616d1388a9e46e09c07339f0f5e50a2.png]: https://img-blog.csdnimg.cn/6616d1388a9e46e09c07339f0f5e50a2.png