优先级队列（概念理解/底层模拟/时间复杂度分析）

在之前的数据结构学习中，我们都知道队列是一个先进先出（FIFO）的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。

在这种情况下，数据结构应该提供两个最基本的操作，一个是每次优先返回优先级高的对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。

2.优先级队列的底层模拟

在JDK1.8中，PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。

2.1堆的概念

在我们之前学习中直到，二叉树可以进行链式存储，而堆本质上也是一种二叉树，不过它的存储方式不在是链式存储，而是顺序存储（存储在数组中）。

那么一个数组如何表示一颗二叉树呢？

如图，采用一个层序遍历的方式就可以了：

大家可以在仔细观察一下这棵二叉树有什么特点？

没错，在这颗树中：

1.每个节点的左右两个子节点所储存的值都要比双亲节点（父亲节点）储存的值要大。

2.这是一颗完全二叉树。

实际上，上面这棵树就是一个堆。

堆分为大根堆以及小根堆。

像这种某个节点的值总是不小于其父节点的值，我们称为小根堆。

如图：

另外，某一个节点的值总是不大于其父节点的值，我们称之为大根堆

如图：

注意：只要是堆，那么他一定是完全二叉树

因为堆是顺序存储的，如果不是一颗完全二叉树，会出现这种情况：

数组中会有很多空间没有被利用。

而完全二叉树恰好能避免这种情况，实现数据的高效存储

2.2优先队列的模拟实现

想要实现优先队列，实际上就是要创建一个堆，对堆，进行相关的操作。

不过想要用顺序存储这样一个数据结构，好像有亿点难ε=(´ο｀*)))唉。

那么它真的很难吗？

如果你已经学过二叉树的基本操作了，那么你可以大胆的对别人说这个堆，它其实亿点也不难ƪ(˘⌣˘)ʃ

优先级队列的底层是堆

堆的底层就是一个数组

下面以大根堆为例，创建一个数组对数组进行操作，进而实现优先级队列

2.2.1把Heap类定义好

class BigHeap {

    int[] elem;
    int useSize;//堆的大小，默认为0

    public BigHeap() {//调用构造方法，数组默认容量是10，不够之后再考虑扩容
        this.elem = new int[10];
    }

    public void init(int[] array) {

    }

    public void creatHeap() {

    }

    public void siftDonw(int parent, int end) {

    }

    public void offer(int val) {

    }

    public void siftUp(int child) {

    }

    public boolean isFull() {
        return false;
    }

    public boolean isEmpty() {
        return false;
    }

}

下面，我们依次实现各种操作方法：

2.2.2初始化堆

    public void init(int[] array) {
        if(array.length>elem.length){//所给的数组大小，比预先堆中的大，要对堆扩容
            Arrays.copyOf(elem,array.length+elem.length);
        }
        for (int i = 0; i <array.length ; i++) {
            elem[i]=array[i];
            useSize++;//使用量，每次加一
        }
    }

2.2.3创建大堆

在此之前，你要掌握一下知识：

在顺序存储的二叉树中：

parent=(child-1)/2----->不论是左孩子，还是右孩子，计算出的都是他们同一个父节点

leftChild=parent*2+1

rightChild=parent*2+1

1.思路

在初始化的时候，我们已经得到了一个完全二叉树。

想要创建大堆，那么这颗完全二叉树的每个子节点的值都不能大于父节点的值。

其实，实现它也很简单。

第一步：

使用一个算法（向下调整算法），当对某一个节点（子树）完成这个算法的时候，这颗子树就变成了一个大根堆

第二步

从这颗初始化的完全二叉树的最后一个父节点【lastParent=((elem.length-1)-1)/2】开始

使用第一步的算法，然后父节点，在跳转到父节点的父节点继续使用该算法，直到遍历到树的root节点为止。

这时，此树就是大根堆了

以此二叉树为例：

图文理解：

从最后一个父节点（度不为0的）也就是9，到根节点（也就是3）

所以，一共要进行四次向下调整算法。

第一次向下调整：

解释：

从9节点开始向下比较。

1. 先对13和12进行比较（先对孩子节点比较）

2. 因为13>12，所以13在对9比较。

3. 9<13，所以9和13要交换

由于如果在往下比较，父节点就没有子节点了，所以直接进行第二次向下调整算法：

解释：

Dad倒着往上依次遍历，使用向下调整算法，所以这时，Dad指向7位置

与第一次向下调整算法一样

7和12交换，然后直接进行第三次向下调整算法

第三次向下调整算法：

解释：

Dad倒着往上依次遍历，使用向下调整算法，所以这时，Dad指向5位置

5小于最大的孩子节点13，所以13和5进行交换

如图：

此时我们还在进行第三次向下调整，因为当前的5节点的左右孩子都存在因此还要进行比较

在虚线中三个节点，12最大，12和5交换，然后第三次向下调整结束。

第四次向下调整：

解释：

Dad倒着往上依次遍历，使用向下调整算法，所以这时，Dad指向3位置

上图，解同样地，按部就班，13和3交换

上图同样地，3和12交换

上图同样地，3和9交换

然后大根堆就出来了：

2.思路转化为代码

 public void creatHeap() {

        for (int i =((useSize-1)-1)/2; i >=0 ; i--) {
            siftDown(i,useSize-1);//从后往前，全部使用一次向下调整算法
        }
    }


    private void swap(int a,int b){
        int t;
        t=elem[a];
        elem[a]=elem[b];
        elem[b]=t;
    }
    public void siftDown(int parent, int end) {//parent end都是有效下标

        int child=2*parent+1;//默认是左孩子
        while(child<=end){//调整到最后一个子节点，为止
            //先判断是否有右孩子
            if(child+1<=end){//如果有判断谁大，大的当左孩子
                if(elem[child]<elem[child+1]){
                    swap(child,child+1);
                }
            }

            //左孩子在和父节点进行比较
            if(elem[child]>elem[parent]){//如果孩子节点大，那么父子交换位置
                swap(child,parent);
            }else{
                break;//如果父节点已经是最大的就不用调整了，这棵树就是大根堆
                //因为我们会从后往前，把这棵树（数组）一次遍历调整完
            }
            //下面继续往往下面调整
            parent=child;//当前的父亲，变成自己的孩子
            child=parent*2+1;//孩子变成孩子的孩子
        }
    }

2.2.4堆操作之offer（进队列）

1.思路

把要进队的元素放到数组最后一个元素后面：

他进行向上调整一次就OK喽

假设进队元素==13：

向上调整：

和向下调整一样，只是顺序变成了自上而下。

需要进队的元素先与父节点比较，

如果进队元素更大，就交换，然后子节点变成父节点，父节点，变成父节点的父节点，依次比较到根。

一旦父节点比孩子节点都大，那么就退出

调整后的大根堆：

2.思路转化为代码：

 public void siftUp(int child) {
        int parent=(child-1)/2;
        while(parent>=0){
            if(elem[parent]<elem[child]){//孩子节点，大，那么就交换
                swap(elem[parent],elem[child]);
                child=parent;//向上继续比较
                parent=(child-1)/2;//向上继续比较
            }else{//否则调整完毕，直接跳出（因为本身就是一个大根堆）
                break;
            }
        }
    }

2.2.5堆操作之poll（删除）

注意：堆的删除一定是删除堆顶元素！

思路：

1.堆顶元素和最后一个元素进行交换

2.堆的有效个数减少一个

3.对堆顶元素进行一次向下调整

图片演示：

思路转化为代码：

 public int poll(){
        if(isEmpty())return -1;//如果堆是空的，返回一个无效值

        //删除一定是删除除堆顶元素

        //堆顶元素和最后一个元素交换位置，useSize--,然后对堆顶元素进行一次向下调整即可
        swap(0,useSize-1);

        siftDown(0,useSize-1);

        useSize--;

        return elem[useSize];//返回被poll出来的元素值

    }

2.2.6 isFuLL和isEmpty

两个都很简单，也没什么好说的


    public boolean isFull() {
        if(useSize>=elem.length)return true;
        return false;
    }

    public boolean isEmpty() {
        if(useSize==0)return true;
        return false;
    }

2.3建堆的时间复杂度

考虑最坏情况，那么这颗树就是一个满二叉树，并且是一个小根堆（以大根堆为例）。

进而可以简化证明过程：

当到了第h层时：

有2^(n-1)个节点，要向下移动0层

当然，实际上我们上面的程序是从第h层开始执行的，不过这都一样。

它的时间复杂度就可以变成这样：

通过观察我们发现，这其实就是等差乘等比的形式，错位相减法，就能求出项数和。

最终：建堆的时间复杂度为O(N)

完

原文地址:https://blog.csdn.net/2301_80636143/article/details/138057977 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1782405010785701888.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部