PriorityQueue(优先级队列总结)

怼烎@ 2023-10-02 14:21 9阅读 0赞

### 一，概念 ###

>  *  **队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列**
>  *  **数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)**

### 二，PriorityQueue的特性 ###

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

### 三，使用时的注意事项 ###

> **1. 使用时必须导入PriorityQueue所在的包**
> 
>     import java.util.PriorityQueue;
> 
> **2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常**
> 
> **3. 不能插入null对象，否则会抛出NullPointerException**
> 
> **4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容**
> 
> **5. 插入和删除元素的时间复杂度为![\\log\_\{2\}N][log_2_N]**
> 
> **6. PriorityQueue底层使用了堆数据结构**
> 
> **7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素**

### 四，PriorityQueue的构造器（三种） ###

import java.util.PriorityQueue;
    
    public class MyPriorityQueue {
        public static void method1(){
            //不添加初始容量  默认为11
            PriorityQueue<Integer> p1 = new PriorityQueue<>();
    
            //添加初始容量为100
            PriorityQueue<Integer> p2 = new PriorityQueue<>(100);
    
            p1.offer(1);
            p1.offer(2);
            p1.offer(3);
            p1.offer(4);
            p1.offer(5);
    
            //使用集合容器来进行构造
    
            PriorityQueue<Integer> p3 = new PriorityQueue<>(p1);
    
            System.out.println(p3.peek());
            System.out.println(p3.size());
        }
    
        public static void main(String[] args) {
            method1();
        }
    }

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16][]

**默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器**

public static void method2(){
            PriorityQueue<Integer> p1 = new PriorityQueue<>();
    
            p1.offer(10);
            p1.offer(12);
            p1.offer(14);
            p1.offer(16);
            p1.offer(18);
    
            System.out.println(p1.peek());
    
            PriorityQueue<Integer> p2 = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2 - o1;
                }
            });
    
            p2.offer(10);
            p2.offer(12);
            p2.offer(14);
            p2.offer(16);
            p2.offer(18);
    
            System.out.println(p2.peek());
        }

### ![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16 1][]   五，插入/删除/获取优先级队列的元素以及使用 ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_6_color_FFFFFF_t_70_g_se_x_16][]![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_6_color_FFFFFF_t_70_g_se_x_16 1][]

public static void method3(){
            PriorityQueue<Integer> p = new PriorityQueue<>();
    
            p.offer(1);
            p.offer(2);
            p.offer(3);
            p.offer(4);
            p.offer(5);
    
            System.out.print(p.size() + " ");
            System.out.println(p.peek());
    
            p.poll();
            p.poll();
    
            System.out.print(p.size() + " ");
            System.out.println(p.peek());
    
            p.poll();
            p.poll();
            p.poll();
    
            System.out.print(p.size() + " ");
            System.out.print(p.peek() + " ");
            System.out.println(p.poll() + " ");
            if (p.isEmpty()){
                System.out.println("p is empty!");
            }else{
                System.out.println("p is not empty!");
            }
        }

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

### 六，堆 ###

#### 1.什么是堆 ####

> **JDK1.8中的PriorityQueue底层使用了堆的数据结构，而堆实际就是在完全二叉树的基础之上进行了一些元素的调整。**  
> **堆的性质：**
> 
>  *  堆中某个节点的值总是不大于或不小于其父节点的值；
>  *  堆总是一棵完全二叉树

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_19_color_FFFFFF_t_70_g_se_x_16][]

#### 2.堆的存储方式 ####

**堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储，**  
**注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中须要存储空节点，就会导致空间利用率比较低**

> **将元素存储到数组中后，可以根据二叉树章节的性质5对树进行还原。假设i为节点在数组中的下标，则有：**
> 
>  *  如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
>  *  如果2 \* i + 1 小于节点个数，则节点i的左孩子下标为2 \* i + 1，否则没有左孩子
>  *  如果2 \* i + 2 小于节点个数，则节点i的右孩子下标为2 \* i + 2，否则没有右孩子

#### 3.堆的创建 ####

**向下调整**

public void shiftDown(int[] array,int parent){
            int child = parent * 2 + 1;
            int size = array.length;
    
            while(child < size){
                if ((child + 1 < size) && (array[child + 1] < array[child])){
                    child = child + 1;
                }
    
                if (array[parent] <= array[child]){
                    break;
                }else{
                    int temp = array[parent];
                    array[parent] = array[child];
                    array[child] = temp;
                    parent = child;
                    child = parent * 2 + 1;
                }
            }
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
        }

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

**堆的创建**

//堆的创建
        public void createHeap(int[] array){
            int root = ((array.length - 2) >> 1);
            for (int i = root; i >= 0 ; i--) {
                shiftDown(array,root);
            }
        }

#### 堆的插入与删除 ####

**向上调整**

public void shiftUp(int child) {
            // 找到child的双亲
            int parent = (child - 1) / 2;
            while (child > 0) {
                // 如果双亲比孩子大，parent满足堆的性质，调整结束
                if (array[parent] > array[child]) {
                    break;
                }
                else{// 将双亲与孩子节点进行交换
                    int t = array[parent];
                    array[parent] = array[child];
                    array[child] = t;
                // 小的元素向下移动，可能到值子树不满足对的性质，因此需要继续向上调增
                    child = parent;
                    parent = (child - 1) / 1;
                }
            }
        }

[log_2_N]: https://latex.csdn.net/eq?%5Clog_%7B2%7DN
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/613319d716f14fffa51ab4da9f6cd012.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/b471e9d4940c4ce68ad5a25d0127c208.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_6_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/ff8eec9fa32d4f61ba2495a9c0ee1f0d.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_6,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_6_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/5deb1352180f4f668faba14beca224d3.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_6,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/7105f9fc2df34efcba27c609f8fb51f4.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_19_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/a9188aa3e4c84bdbab8aa422553cdde9.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_19,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/89f63328d5544372a1715c5822a9d87a.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16