【DS】7.PriorityQueue大总结！！

阳光穿透心脏的1/2处 2024-04-03 14:16 75阅读 0赞

##  ##

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

*  
 *   *  一、PriorityQueue简介
     *   *  PriorityQueue是什么
         *  它与其他集合的关系
     *  二、PriorityQueue的使用注意事项【结合源码深入剖析】
     *  三、使用集合建立大根堆代码实现
     *   *  自定义类的情况
         *  常用包装类的情况
         *  比较器实现的方法总结
     *  四、PriorityQueue的模拟实现

### 一、PriorityQueue简介 ###

#### PriorityQueue是什么 ####

![查看源图像][format_png]

中文名字叫做优先级队列，可以理解为队列的Plus 版本，提供返回最高级优先对象和添加新对象等功能。

在优先队列中，每个值都有优先度，优先度高的值排在前面（相等的优先度用与普通队列一样先进先出的顺序打破平局）

> 应用场景举例:  
> 比如一个电商网站搞特卖或抢购，用户登录下单提交后，考虑这个时间段用户访问下单提交量很大，通常表单提交到服务器后端后，后端程序一般不直接进行扣库存处理，将请求放到队列列，异步消费处理，用普通队列是FIFO的，这里有个需求是，用户会员级别高的，可以优先抢购到商品，可能这个时间段的级别较高的会员用户下单时间在普通用户之后，这个时候使用优先队列代替普通队列，基本能满足我们的需求。

#### 它与其他集合的关系 ####

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bqxAOXfQ-1666083189560)(F:\\typora插图\\image-20221016162305289.png)\]][img-bqxAOXfQ-1666083189560_F_typora_image-20221016162305289.png]

### 二、PriorityQueue的使用注意事项【结合源码深入剖析】 ###

1.  **使用时必须导入PriorityQueue所在的包。**
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XDFpMiFH-1666083189589)(F:\\typora插图\\image-20221018142337361.png)\]][img-XDFpMiFH-1666083189589_F_typora_image-20221018142337361.png]
2.  PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常。
    
    假设传入类的对象并没提供比较的方法。可以发现它并没有报错。
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-liOejFp5-1666083189593)(F:\\typora插图\\image-20221018143127684.png)\]][img-liOejFp5-1666083189593_F_typora_image-20221018143127684.png]  
    但是当我们再往里边放元素时就会发现，它报错了。
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-0uw39nGI-1666083189595)(F:\\typora插图\\image-20221018143332006.png)\]][img-0uw39nGI-1666083189595_F_typora_image-20221018143332006.png]
    
    【这里可以去从它的构造方法开始看，但是由于我后边还会再提，并且主要问题不在这，所以这里就没有解释】
    
    根据报错，我们去源码中定位offer方法、siftUpComparable和siftUp方法。看到底是什么原因导致再次offer失败。
    
    ———————————————————————![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SfdF7n5w-1666083189597)(F:\\typora插图\\image-20221018143950446.png)\]][img-SfdF7n5w-1666083189597_F_typora_image-20221018143950446.png]  
    ——————————————————————— ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-20FgqWuU-1666083189598)(F:\\typora插图\\image-20221018144343288.png)\]][img-20FgqWuU-1666083189598_F_typora_image-20221018144343288.png]  
    ———————————————————————
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zoXvaH53-1666083189599)(F:\\typora插图\\image-20221018144713872.png)\]][img-zoXvaH53-1666083189599_F_typora_image-20221018144713872.png]
    
    看到这里我们可以发现在传入第二个元素的时候，必须要经过比较，这也就是我们为什么要求传入的对象必须是可比较的。
    
    那问题又来了，到底怎么实现这个类是可比较的呢？
    
    对于java已经提供的包装类，这个问题我们不需要特别考虑（除非你自己重新定义比较规则了）；
    
    但是对于自定义类，就需要我们实现Comparable接口，重写compareTo方法了。
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5PBAYO1m-1666083189600)(F:\\typora插图\\image-20221018145217866.png)\]][img-5PBAYO1m-1666083189600_F_typora_image-20221018145217866.png]
    
    下边来测试一下
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RG69l8MK-1666083189601)(F:\\typora插图\\image-20221018145902997.png)\]][img-RG69l8MK-1666083189601_F_typora_image-20221018145902997.png]
3.  与List等集合不同，它不能插入null对象，否则会抛出NullPointerException
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cwHC9K3y-1666083189602)(F:\\typora插图\\image-20221018150609324.png)\]][img-cwHC9K3y-1666083189602_F_typora_image-20221018150609324.png]
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Nb0Afh8n-1666083189603)(F:\\typora插图\\image-20221018150703374.png)\]][img-Nb0Afh8n-1666083189603_F_typora_image-20221018150703374.png]
4.  **没有容量限制**，可以插入任意多个元素，其内部可以自动扩容
    
    它跟源码中offer方法和grow方法的定义有关。
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HQH1LjRA-1666083189604)(F:\\typora插图\\image-20221018151453390.png)\]][img-HQH1LjRA-1666083189604_F_typora_image-20221018151453390.png]
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Tdf4UU81-1666083189605)(F:\\typora插图\\image-20221018151803025.png)\]][img-Tdf4UU81-1666083189605_F_typora_image-20221018151803025.png]
5.  插入和删除元素的时间复杂度为O(logn)。
    
    首先看插入即offer
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kyjMH2Kt-1666083189605)(F:\\typora插图\\image-20221018152615726.png)\]][img-kyjMH2Kt-1666083189605_F_typora_image-20221018152615726.png]
    
    下边来看poll
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-He5zV3l6-1666083189606)(F:\\typora插图\\image-20221018152953469.png)\]][img-He5zV3l6-1666083189606_F_typora_image-20221018152953469.png]
6.  PriorityQueue底层使用了堆数据结构
    
    最起码从这几个方法中就可以看出来
    
    ![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-1a3wD48Q-1666083189606)(F:\\typora插图\\image-20221018153309704.png)\]][img-1a3wD48Q-1666083189606_F_typora_image-20221018153309704.png]
7.  PriorityQueue**默认情况下是小堆**—即每次获取到的元素都是最小的元素

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-b2W9kC0N-1666083189607)(F:\\typora插图\\image-20221018153552145.png)\]][img-b2W9kC0N-1666083189607_F_typora_image-20221018153552145.png]

那么问题就来了，我们怎么利用集合创建一个大根堆呢？我们总有用到这种情况的场景。这个问题我们将会在下部分讨论

接下来，我们总结一下PriorityQueue中使用频率相对来讲高的方法：

**构造方法**

<table> 
 <thead> 
  <tr> 
   <th>构造器</th> 
   <th>功能</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>PriorityQueue()</td> 
   <td>创建一个空的优先级队列，默认容量是11</td> 
  </tr> 
  <tr> 
   <td>PriorityQueue(int initialCapacity)</td> 
   <td>创建一个初始容量为initialCapacity的优先级队列，注意： initialCapacity不能小于1，否则会抛IllegalArgumentException异常</td> 
  </tr> 
  <tr> 
   <td>PriorityQueue(Collection&lt;? extends E&gt; c)</td> 
   <td>用一个集合来创建优先级队列</td> 
  </tr> 
 </tbody> 
</table>

此处我们再看看构造方法的源码：

【重点看前两个，后一个本人水平有限，解释不明白】

在不指定默认容量的时候，怎么实现向里边offer元素的呢？

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-s3eHYM4A-1666083189608)(F:\\typora插图\\image-20221018154019189.png)\]][img-s3eHYM4A-1666083189608_F_typora_image-20221018154019189.png]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XbB0EerG-1666083189609)(F:\\typora插图\\image-20221018154036233.png)\]][img-XbB0EerG-1666083189609_F_typora_image-20221018154036233.png]

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Zjzoaohh-1666083189610)(F:\\typora插图\\image-20221018154132383.png)\]][img-Zjzoaohh-1666083189610_F_typora_image-20221018154132383.png]

**增删查改相关方法**

<table> 
 <thead> 
  <tr> 
   <th>方法</th> 
   <th>功能</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>boolean offer(E e)</td> 
   <td>插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时 间复杂度O(logn)，注意：空间不够时候会进行扩容</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> 
 </tbody> 
</table>

### 三、使用集合建立大根堆代码实现 ###

PriorityQueue默认情况下是小堆，如果我们需要建立大根堆。

#### 自定义类的情况 ####

对于自定义类，我们可以通过实现Comparable接口、重写compareTo方法或者提供比较器两种办法实现，（一般是重写compareTo方法）。前者直接使用无参构造即可，后者需要调用带比较器参数的构造方法，传入比较器。下面来举个例子【比较器的在下边举例】。

//实现Comparable接口、重写compareTo方法
    class Student implements Comparable<Student>{
        
        int id;
        double score;
        public Student(int id) {
        
            this.id = id;
        }
    
        @Override
        //是在自定义类中重写
        public String toString() {
        
            return "Student{" +
                    "id=" + id +
                    ", score=" + score +
                    '}';
        }
        @Override
        public int compareTo(Student o) {
        
            return o.id-this.id;
        }
    
    }
    public class Test {
        
        public static void main(String[] args) {
        
            PriorityQueue<Student> priorityQueue=new PriorityQueue<>();
            priorityQueue.offer(new Student(111));
            priorityQueue.offer(new Student(112));
            priorityQueue.offer(new Student(110));
            priorityQueue.offer(new Student(95));
            System.out.println(priorityQueue);
            System.out.println("abcd");
        }
    }

#### 常用包装类的情况 ####

但对于Integer这样的自带的包装类，我们没有办法改变源码，没有办法在类内部重写compareTo方法。所以这时，我们必须重新实现一个符合我们逻辑的比较器。也是一样我们来举个例子。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Sk6V59Hx-1666083189611)(F:\\typora插图\\image-20221018160558499.png)\]][img-Sk6V59Hx-1666083189611_F_typora_image-20221018160558499.png]

class InCmp implements Comparator<Integer>{
        
        @Override
        public int compare(Integer o1, Integer o2) {
        
            //默认是升序o1-o2
            //我们的要求是降序——o1-o2
            return o2-o1;
        }
    }
    public class Test2 {
        
        public static void main(String[] args) {
        
            InCmp intCmp=new InCmp();
            PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(5,intCmp);
            priorityQueue.offer(1);
            priorityQueue.offer(6);
            priorityQueue.offer(-5);
            priorityQueue.offer(7);
            priorityQueue.offer(4);
            System.out.println(priorityQueue);
        }
    }

#### 比较器实现的方法总结 ####

1.  单独写一个类，之后实例化对象，传参到构造方法中。【即第二个例子】
2.  比较器的匿名内部类写法。【比较常用，推荐】
3.  lambda表达式写法【jdk1.8特性之一，了解即可】

下边我们就匿名内部类进行举例

**匿名内部类：**

//匿名内部类
    class InCmp implements Comparator<Integer>{
        
        @Override
        public int compare(Integer o1, Integer o2) {
        
            //默认是升序o1-o2
            //我们的要求是降序——o1-o2
            return o2-o1;
        }
    }
    public class Test2 {
        
        public static void main(String[] args) {
        
            InCmp intCmp=new InCmp();
            PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(5,intCmp);
            priorityQueue.offer(1);
            priorityQueue.offer(6);
            priorityQueue.offer(-5);
            priorityQueue.offer(7);
            priorityQueue.offer(4);
            System.out.println(priorityQueue);
    
            PriorityQueue<Integer> priorityQueue2=new PriorityQueue<Integer>(new Comparator<Integer>() {
        
                @Override
                public int compare(Integer o1, Integer o2) {
        
                    return o2-o1;
                }
            }){
        
    
            };
            priorityQueue2.offer(1);
            priorityQueue2.offer(6);
            priorityQueue2.offer(-5);
            priorityQueue2.offer(7);
            priorityQueue2.offer(4);
            System.out.println("匿名内部类写法："+priorityQueue);
        }
    }

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eMHZDpXC-1666083189611)(F:\\typora插图\\image-20221018161817208.png)\]][img-eMHZDpXC-1666083189611_F_typora_image-20221018161817208.png]

### 四、PriorityQueue的模拟实现 ###

关于具体思路分析，可以参考我之前对堆的总结

[堆的基本概念及常用操作实现][Link 1]

public class MyHeap {
        
        public int[]elem;
        public int usedSize;
    
        public MyHeap() {
        
            this.elem = new int[10];
        }
        public void initElem(int[]array){
        
            for (int i = 0; i < array.length; i++) {
        
                elem[i]=array[i];
                usedSize++;
            }
        }
        public void createHeap(){
        
            for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
        
                shitDownBig(parent,usedSize);
            }
        }
        private void shitDownBig(int parent, int len){
        
            int child=2*parent+1;
            while(child<len){
        
                if((child+1<len)&&(elem[child]<elem[child+1])){
        
                    child++;
                }
                if(elem[child]>elem[parent]){
        
                    int tmp=elem[child];
                    elem[child]=elem[parent];
                    elem[parent]=tmp;
                    parent=child;
                    child=2*parent+1;
                }else{
        
                    break;
                }
            }
        }
        private void shitDownSmall(int parent, int len){
        
            int child=2*parent+1;
            while(child<len){
        
                if((child+1<len)&&(elem[child]>elem[child+1])){
        
                    child++;
                }
                if(elem[child]<elem[parent]){
        
                    int tmp=elem[child];
                    elem[child]=elem[parent];
                    elem[parent]=tmp;
                    parent=child;
                    child=2*parent+1;
                }else{
        
                    break;
                }
            }
        }
        //堆的插入
        public void offer(int val){
        
            if(isFull()){
        
                elem= Arrays.copyOf(elem,elem.length*2);
            }
            this.elem[usedSize++]=val;
            shitUp(usedSize-1);
        }
        private void shitUp(int child){
        
            int parent=(child-1)/2;
            while(child>0){
        
                if(elem[child]>elem[parent]){
        
                    int tmp=elem[child];
                    elem[child]=elem[parent];
                    elem[parent]=tmp;
                    child=parent;
                    parent=(parent-1)/2;
                }else{
        
                    break;
                }
            }
        }
        public boolean isFull(){
        
            return usedSize==elem.length;
        }
        public int pop(){
        
            if(isEmpty()){
        
                return -1;
            }
            int tmp=elem[0];
            elem[0]=elem[usedSize-1];
            elem[--usedSize]=tmp;
            shitDownBig(0,usedSize);
            return tmp;
        }
        public boolean isEmpty(){
        
            return usedSize==0;
        }
        public int peek(){
        
            if(isEmpty()){
        
                return -1;
            }
            return elem[0];
        }
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly93eDIuc2luYWltZy5jbi9sYXJnZS9iOTA1YWE2Nmx5MWc2Z3puZ3MxMnhqMjBpNzA5M2RoNy5qcGc?x-oss-process=image/format,png
[img-bqxAOXfQ-1666083189560_F_typora_image-20221016162305289.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b88e54b26d2d423dbb5bc1e89b1db16b.png
[img-XDFpMiFH-1666083189589_F_typora_image-20221018142337361.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/1cc37fe819ed4c2081035de4ce103b57.png
[img-liOejFp5-1666083189593_F_typora_image-20221018143127684.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/2bf383adbf0a480d9cc6d7a4b13a381c.png
[img-0uw39nGI-1666083189595_F_typora_image-20221018143332006.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/97ea054c0a7d4f169e5aa45dd723a5b0.png
[img-SfdF7n5w-1666083189597_F_typora_image-20221018143950446.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/3bf9d1efb5024902909a3210c2e86b82.png
[img-20FgqWuU-1666083189598_F_typora_image-20221018144343288.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/ccbf8357c9f94d56a0775239c17094ea.png
[img-zoXvaH53-1666083189599_F_typora_image-20221018144713872.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/c70cf52326f84f63b600b4ea6ea0fa52.png
[img-5PBAYO1m-1666083189600_F_typora_image-20221018145217866.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/bed3aea64ff84f7ca8bf16dfdd45cad1.png
[img-RG69l8MK-1666083189601_F_typora_image-20221018145902997.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/db1ee32de7e14b87b3e60221c7c4701a.png
[img-cwHC9K3y-1666083189602_F_typora_image-20221018150609324.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/9656b1c39673424aac8e95044da79bed.png
[img-Nb0Afh8n-1666083189603_F_typora_image-20221018150703374.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/503d5d0406384b0dab5a8d8d3a2db578.png
[img-HQH1LjRA-1666083189604_F_typora_image-20221018151453390.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/b19a819e29ca4a118893101b91e4ac46.png
[img-Tdf4UU81-1666083189605_F_typora_image-20221018151803025.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/0dcf4dda947548c2838c16fcfdeec65a.png
[img-kyjMH2Kt-1666083189605_F_typora_image-20221018152615726.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/903e08f0e63d48919aa948a4cc823f49.png
[img-He5zV3l6-1666083189606_F_typora_image-20221018152953469.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/9f8e2aff735d4ecaa4d310c2ea96d75e.png
[img-1a3wD48Q-1666083189606_F_typora_image-20221018153309704.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/76fc99ac9ff842be94bf19d66760abd2.png
[img-b2W9kC0N-1666083189607_F_typora_image-20221018153552145.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/70a30f2c15744012b63e63ec380e2add.png
[img-s3eHYM4A-1666083189608_F_typora_image-20221018154019189.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/3f0e0a49f06d4905849e35dddcfa3244.png
[img-XbB0EerG-1666083189609_F_typora_image-20221018154036233.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/987281295937440c887bc5ef6c25b86e.png
[img-Zjzoaohh-1666083189610_F_typora_image-20221018154132383.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/acd7ea0050f54f2c86fc148b34a56732.png
[img-Sk6V59Hx-1666083189611_F_typora_image-20221018160558499.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/8ec7fec80b6247888defaa1bd1e55e60.png
[img-eMHZDpXC-1666083189611_F_typora_image-20221018161817208.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/fd7874d0195849229ba6e4a81475a845.png
[Link 1]: http://t.csdn.cn/Y1pRB