【DS】7.PriorityQueue大总结！！_.net7 priorityqueue

一、PriorityQueue简介

PriorityQueue是什么

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

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

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

它与其他集合的关系

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

1. 使用时必须导入PriorityQueue所在的包。

   

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

   假设传入类的对象并没提供比较的方法。可以发现它并没有报错。

   
   但是当我们再往里边放元素时就会发现，它报错了。

   

   【这里可以去从它的构造方法开始看，但是由于我后边还会再提，并且主要问题不在这，所以这里就没有解释】

   根据报错，我们去源码中定位offer方法、siftUpComparable和siftUp方法。看到底是什么原因导致再次offer失败。

   ———————————————————————
   ———————————————————————
   ———————————————————————

   

   看到这里我们可以发现在传入第二个元素的时候，必须要经过比较，这也就是我们为什么要求传入的对象必须是可比较的。

   那问题又来了，到底怎么实现这个类是可比较的呢？

   对于java已经提供的包装类，这个问题我们不需要特别考虑（除非你自己重新定义比较规则了）；

   但是对于自定义类，就需要我们实现Comparable接口，重写compareTo方法了。

   

   下边来测试一下

   

3. 与List等集合不同，它不能插入null对象，否则会抛出NullPointerException

   

   

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

   它跟源码中offer方法和grow方法的定义有关。

   

   

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

   首先看插入即offer

   

   下边来看poll

   

6. PriorityQueue底层使用了堆数据结构

   最起码从这几个方法中就可以看出来

   

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

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

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

构造方法

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

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

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

增删查改相关方法

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

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");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

常用包装类的情况

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

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
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

比较器实现的方法总结

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);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

四、PriorityQueue的模拟实现

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

堆的基本概念及常用操作实现

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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97