【数据结构】优先级队列（堆）

骑猪看日落 2024-03-01 08:19 108阅读 0赞

> **作者主页：[paper jie\_博客][paper jie]**
> 
> **本文作者：大家好，我是paper jie，感谢你阅读本文，欢迎一建三连哦。**
> 
> **本文录入于《JAVA数据结构》专栏，本专栏是针对于大学生，编程小白精心打造的。笔者用重金(时间和精力)打造，将javaSE基础知识一网打尽，希望可以帮到读者们哦。**
> 
> **其他专栏：《算法详解》《C语言》《javaSE》等**
> 
> **内容分享：本期将会分享数据结构中的优先级队列**

## 优先级队列 ##

我们了解过的队列，是一种**先进先出**的数据结构。但是呢，在有些情况下，数据的出入是有优先级的，一般出队时，可能需要优先级高的元素先出队列，在这种场景下，使用队列就不合适了。优先级就比如：我们使用手机玩游戏的时候，有电话打过来的时候，手机就要先处理打过来的电话。

在这种情况下，我们就应该提供两种基本的操作，**返回最高优先级对象和新增对象**。这种数据结构就是优先级队列。

## 优先级队列的模拟实现 ##

在**JDK1.8中的priorityQueue底层使用了堆这种数据结构**，而这个堆又是在完全二叉树的基础上进行的调整。

### 什么是堆 ###

如果有一个关键码的集合K = \{k0，k1， k2，…，kn-1\}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆

**堆的性质：**

**堆中某个节点的值总是不大于(小根堆) 或者不小于(大根堆) 其父节点的值**

**堆一定是一颗完全二叉树**

![00a79abc587447fcbea5a8a9a535a9cd.png][]

### 堆的存储方式 ###

**堆是一颗完全二叉树，可以用层序的规则采用顺序的方式来高效存储**

![f7710c7d007e4597af1ea570c4aaed0c.png][]

这里要注意：对于不是完全二叉树的，就不适合使用顺序存储了，因为要还原二叉树，就要将空节点也保存，这样子就会浪费空间，空间利用率低。

**我们可以根据以下二叉树的性质来还原二叉树：**

**如果i为0，表示的节点为根结点，否则i节点的双亲节点为（i - 1）/ 2**

**如果2 \* i + 1 小于节点个数，则节点i的左孩子下标为2 \* i + 1,否则没有左孩子**

**如果2 \* i + 2 小于节点个数， 则节点i的右孩子下标为2 \* i + 1，否则没有右孩**子

### 堆的创建 ###

这里创建堆的方式是使用向下调整的方式来建堆的。想法就是从堆的最后一个节点的父结点开始向下调整，调整完后再向前一个节点向下调整，依次不断到0下标的节点调整完后就算建堆成功了。

**画图分析：**

![9cf0f4033e084a529b52880c29038cb7.png][]

![0ae1038064b84564b09ae015ddded141.png][]

### 建堆的时间复杂度分析 ###

这里我们考虑最坏的情况即是一颗满叉树且每一个节点都要调整

**画图分析：**

![4df1d1ebc5d24bb3ac55a43dc3910e2e.png][]

**通过上图得知向上调整的时间复杂度为O(n)**

**向下调整的复杂度会比向上调整的复杂度高上很多，不建议使用它来建堆**

**原因：**

**我们知道向上调整是从最后一层的最后一个节点开始，而向下调整只需要从倒数第二层的最后一个节点开始，而往往最后一层的节点就基本等于前面全部节点加起来之和-1**

### 堆的插入和删除 ###

#### 堆的插入 ####

**堆的插入就只有4个步骤：**

**检查空间大小**

**将需插入节点放入最后一个位置**

**再从最后一个位置开始向上调整**

**最后有效位置加一**

**画图分析：**

![4bbcc2a06d004dedb702f8a2f3957608.png][]

#### 堆的删除 ####

**注意这里的删除是堆顶的元素。具体步骤：**

**将堆顶元素和堆尾元素交换**

**有效位置减一**

**从堆顶开始向下调整**

**画图分析：**

![a69f43689b794240aaf536d43d9fa4c1.png][]

### 具体代码 ###

import java.util.Arrays;
    
    
    public class MyHeap {
        private int[] elem;
        int usedsize;
    
        public MyHeap() {
            this.elem = new int[10];
        }
    
        //初始化elem数组
        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--) {
                siftDown(parent, usedsize);
            }
        }
    
        private void siftDown(int parent, int len) {
            //左孩子
             int child = 2*parent+1;
    
             while(child < len) {
                 if(child+1 < len && elem[child] < elem[child+1] ) {
                     child += 1;
                 }
    
                 if(elem[child] > elem[parent]) {
                     //交换
                     int temp = elem[child];
                     elem[child] = elem[parent];
                     elem[parent] = temp;
                     parent = child;
                     child = 2*parent+1;
                 }else {
                     break;
                 }
             }
        }
    
        //插入元素
        public void push(int val) {
            //满了
            if(elem.length == usedsize) {
                elem = Arrays.copyOf(elem, elem.length * 2);
            }
    
            elem[usedsize] = val;
    
            siftUp(usedsize);
    
            usedsize++;
        }
        private void siftUp(int child) {
            int parent = (child - 1) / 2;
            while(child > 0 ) {
                if(elem[child] > elem[parent]) {
                    int temp = elem[child];
                    elem[child] = elem[parent];
                    elem[parent] = temp;
                    child = parent;
                    parent = (child - 1) / 2;
                }else {
                    break;
                }
            }
        }
    
        /*
        *
        * 删除元素
        *
        */
    
        public void pop() {
            if(isEmpty()) {
                return ;
            }
    
            int temp = elem[0];
            elem[0] = elem[usedsize-1];
            elem[usedsize-1] = temp;
            usedsize--;
    
            int parent = 0;
            int child = 2 * parent + 1 ;
            while(child < usedsize) {
                if(child+1<usedsize && elem[child] < elem[child+1]) {
                    child+=1;
                }
                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 boolean isEmpty() {
            return usedsize == 0;
        }
    }

## priorityQueue ##

java集合中提供了priorityQueue和priorityBlockingQueue两种类型的优先级队列，priorityQueue是线程不安全的，PriorityQueue是线程安全的。

![27129c14bd9a40478f8752a18b0caef6.png][]

**使用priorityQueue的注意事项:**

**1 使用时必须导入PriorityQueue所在的包：**

import java.util.PriorityQueue;

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

![0d2c477756e64ee09e43b9ed10e9c33b.png][]

**3 不能插入null对象，不然会1抛出nullpointerException**

**没有容量限制，任意插入多个元素，内部会自动扩容**

![f662477f61aa47898f1953f3e9b64011.png][]

**4 插入和删除元素的时间复杂度都是O(logn)**

**5 priorityQueue的底层使用堆数据结构**

**6 priorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素，想要建立大堆需要自己传比较器**

![96903bd40fc34ad0b070bd7e0b42109d.png][]

### priorityQueue的使用 ###

#### 优先级队列的构造方法 ####

![e2d1a59b703f4ab49e18c2d27a79bb94.png][]

![ed3bcc6efc2b45fd963abf3dcc988ef8.png][]

static void TestPriorityQueue(){
    // 创建一个空的优先级队列，底层默认容量是11
    PriorityQueue<Integer> q1 = new PriorityQueue<>();
    // 创建一个空的优先级队列，底层的容量为initialCapacity
    PriorityQueue<Integer> q2 = new PriorityQueue<>(100);
    ArrayList<Integer> list = new ArrayList<>();
    list.add(4);
    list.add(3);
    list.add(2);
    list.add(1);
    // 用ArrayList对象来构造一个优先级队列的对象
    // q3中已经包含了三个元素
    PriorityQueue<Integer> q3 = new PriorityQueue<>(list);
    System.out.println(q3.size());
    System.out.println(q3.peek());
    }

一般在默认的情况下，PriorityQueue队列是小堆，需要变成大堆需要提供比较器：

class IntCmp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
    return o2-o1;
    }
    }

#### 插入，删除，获取优先级最高的元素 ####

![f91a0d8af2ba498a8f13ef334e18fcf7.png][]

static void TestPriorityQueue2() {
            int[] arr = {4, 1, 9, 2, 8, 0, 7, 3, 6, 5};
    // 一般在创建优先级队列对象时，如果知道元素个数，建议就直接将底层容量给好
    // 否则在插入时需要不多的扩容
    // 扩容机制：开辟更大的空间，拷贝元素，这样效率会比较低
            PriorityQueue<Integer> q = new PriorityQueue<>(arr.length);
            for (int e : arr) {
                q.offer(e);
            }
            System.out.println(q.size()); // 打印优先级队列中有效元素个数
            System.out.println(q.peek()); // 获取优先级最高的元素
    // 从优先级队列中删除两个元素之和，再次获取优先级最高的元素
            q.poll();
            q.poll();
            System.out.println(q.size()); // 打印优先级队列中有效元素个数
            System.out.println(q.peek()); // 获取优先级最高的元素
            q.offer(0);
            System.out.println(q.peek()); // 获取优先级最高的元素
    // 将优先级队列中的有效元素删除掉，检测其是否为空
            q.clear();
            if (q.isEmpty()) {
                System.out.println("优先级队列已经为空!!!");
            }
        }

**这里要注意优先级队列扩容说明：**

**如果容量小于64时，就是按oldCapacity的两倍大小来扩容**

**如果容量大于等于64时，就是按oldCapacity的1.5倍大小扩容**

**如果扩容后的容量大小大于整型的最大值，则按整型的最大值来扩容**

![b4fd3646e38e4a808dfbd1b6bce80e72.png][]

## 堆的应用 ##

### 用堆为数据结构来封装优先级队列 ###

Java中的priorityQueue底层就是用堆来实现的

### 堆排序 ###

堆排序就是使用堆的思想来进行排序

**1. 建堆**

升序：建大堆

降序：建小堆

**2. 使用堆元素删除思想来进行排序**

交换堆顶和堆尾元素，然后向下调整

![164b87f1951448dd8b02fdf11ffd7bdd.png][]

[paper jie]: https://blog.csdn.net/paperjie?type=blog
[00a79abc587447fcbea5a8a9a535a9cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/2f0079299d4745c4947c2a29c69b69da.png
[f7710c7d007e4597af1ea570c4aaed0c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/8408ba34a6fa4b6db93aa7dd24455532.png
[9cf0f4033e084a529b52880c29038cb7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/c7b41a85260345e5a0dca985e63bc132.png
[0ae1038064b84564b09ae015ddded141.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/831af20b3aa342a19c42078863cad065.png
[4df1d1ebc5d24bb3ac55a43dc3910e2e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/52e560f45dc54d58bd145d3cb1c3829f.png
[4bbcc2a06d004dedb702f8a2f3957608.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/7dc6aff02f224f29ac5db75d084417da.png
[a69f43689b794240aaf536d43d9fa4c1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/47b6fabc8ab9409b8c2ffba4cd068285.png
[27129c14bd9a40478f8752a18b0caef6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/5a63ab501cf24bdeaa2ce527fa5fff23.png
[0d2c477756e64ee09e43b9ed10e9c33b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/ec44ce770c494c8e99315541edc57126.png
[f662477f61aa47898f1953f3e9b64011.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/1b1c2a460e5249a08833ad7eefd4fc05.png
[96903bd40fc34ad0b070bd7e0b42109d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/1a039e7c92854656a03657633e91fa0c.png
[e2d1a59b703f4ab49e18c2d27a79bb94.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/b405a425164c4462956988b292d4f20d.png
[ed3bcc6efc2b45fd963abf3dcc988ef8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/48a35215f30a474ba9965f65e4fe0a3e.png
[f91a0d8af2ba498a8f13ef334e18fcf7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/a8a9b608f9eb4f4a89098fb90e79a260.png
[b4fd3646e38e4a808dfbd1b6bce80e72.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/a95802732bef4bf4988550ef110ff0ba.png
[164b87f1951448dd8b02fdf11ffd7bdd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/e31c9cf6cb594b4db4d364be78b4c543.png