📕各位读者好, 我是小陈,

这是我的个人主页


📗小陈还在持续努力学习编程, 努力通过博客输出所学知识

📘如果本篇对你有帮助, 烦请点赞关注支持一波, 感激不尽

📙 希望我的专栏能够帮助到你:


JavaSE基础

: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等


Java数据结构

: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等


JavaEE初阶

: 多线程, 网络编程, TCP/IP协议, HTTP协议, Tomcat, Servlet, Linux, JVM等(正在持续更新)


提示：是正在努力进步的小菜鸟一只，如有大佬发现文章欠佳之处欢迎评论区指点~ 废话不多说，直接发车~


一、什么是优先级队列

优先级队列并不是像普通普通的队列那样永远遵从先进先出, 而是有优先级的, 出队时

让优先级高的先出队

🔝

上篇文章说过, 二叉树是一种逻辑结构, 物理结构上可以是顺序存储, 也可以是链式存储, 而

堆就是在顺序存储的二叉树上做了调整

PriorityQueue底层使用了堆这种数据结构

📌📌📌

堆

的概念:

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

👉👉👉说人话:

1, 堆必须是完全二叉树

2, 每一棵树的根节点必须小于/大于左右孩子结点

如图: (小根堆 和 大根堆)

二、模拟实现

👉优先级队列底层是堆, 所以首先我们要实现堆这种数据结构, 堆的操作是在

顺序存储的二叉树

上, 换句话说就是在

数组

上, 所以成员属性只需要一个数组和用来记录长度的 usedSize 即可, 成员方法可以给定一个构造方法用来定义堆的容量大小

👉给定一个数组, 创建成堆, 自然需要把数组里的数据拷贝到堆底层的数组上来组织, 所以再设置一个成员方法用来初始化数组

public class MyPriorityQueue {

    public int[] elem;
    public int usedSize;

    public MyPriorityQueue () {
        this.elem = new int[10];
    }

    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

为什么要模拟实现： 自己模拟实现 简易版的 栈的增删查改等主要功能，大致理解栈的设计思想

再对比学习 Java 提供的集合类当中的 PriorityQueue，在学习 Java 的 PriorityQueue常用方法的同时，也能学习源码的思想

1, 实现堆的基本操作

Java集合中的堆默认是小根堆, 我们模拟实现的堆也是小根堆

1.1, 创建堆

首先我们要把一个无序数组创建成一个堆

1.2.1, 向下调整

把一个无序数组创建成堆的方式是:

向下调整






综上, 向下调整的规则是:

对于小根堆来说: 如果

根结点

大于

左右孩子节点的其中一个


1️⃣ 待调整的结点定义为 parent , 被调整的结点定义为 child

2️⃣ child 选谁? 看图就知道, 是和左右孩子结点较小的那一个调整

3️⃣

如果左右孩子存在的话

, 根节点的下标是 i , 那么左孩子结点的下标就是 2i + 1, 右孩子的结点是2i + 2,

向下调整的代码:

    private void shiftDown(int parent,int len) {
        int child = 2*parent + 1;
        // 有左孩子就进入循环向下调整
        while (child < len) {
            // 如果有右孩子, 令child为较小的孩子结点
            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中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

仅供理解过程及思想, 没有使用泛型, Java中的PriorityQueue是需要使用泛型的, 而向下调整的过程涉及到两个数据的大小比较, 所以在使用PriorityQueue时需要指定对象的比较规则

❗️向下调整的时间复杂度:

最坏情况下就是上图所示, 每调整完一次都需要继续向下调整, 直到树的最后一层(不再有孩子结点), 所以总体来说时间复杂度是O(log₂N)

🚦🚦🚦

了解了向下调整, 对数组建堆就好理解了, 但还有一个需要注意的点, 刚刚向下调整的前提是什么?

前提是,

左右子树已经是小根堆了

, 因为每次向下调整都是要进行比较的, 目的就是为了把更小的数据往堆顶放, 如果左右子树不满足小根堆, 你一趟向下调整, 不一定把最小的放上面了, 那这一趟不是白白浪费了吗

✅✅✅

基于这一点, 对一组无序数据

建堆

的顺序应该是

自下而上

的进行

向下调整


意思就是, 从最底下开始, 让底层的子树通过向下调整的方式建成小根堆, 再逐步往上推进, 这样就能保证每一次向下调整, 当前根结点的左右子树都满足小根堆

如图:

上图过程演示了

自下而上

执行向下调整,

如果某次向下调整导致子树不满足小根堆, 要继续向下调整(如上图最后一步)


上述过程就是一个

从最后一个非叶子结点开始

的循环, 问题是如果编写成代码, 循环的

条件

是什么呢? 如何确定

最后一个非叶子结点的下标

呢?

上图中, 最后一个非叶子结点的下标是3, 最后一个结点就是它的右孩子结点, 下标是8, 那么: (8-1)/2 得到 3 , 正式其父结点的下标, 如果不存在有孩子, 那至少有左孩子, (7-1)/2 得到 3

最后一个非叶子结点的右(左)孩子下标就是数组长度 – 1, 所以确定最后一个非叶子结点的下标方法就是

((array.length-2)>>1);


🚗🚗🚗

观察上图, 什么时候不再需要向下调整呢? 当非叶子结点是0下标的结点时, 退出循环

综上, 建堆的代码如下:

    public void createHeap() {
        for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
            shiftDown(parent,usedSize);
        }
    }

❗️上面说过, 向下调整的时间复杂度是O(log₂N), 而利用向下调整建堆的时间复杂度是O(N)

数学公式推导出来的~

1.2, 堆的插入


堆的操作是在数组上

, 那么插入一个数据应该放在哪里呢?

当然是数组末尾, 那么二叉树就会多出一个叶子节点, 插入数据后仍要保持整棵树是一个大根堆, 那么就需要进行

向上调整


1.2.1, 向上调整

代码如下:

    private void shiftUp(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 = (child-1)/2;
            }else {
                break;
            }
        }
    }	

1.2, 堆的删除

堆的删除是删除

堆顶


(堆顶(最小或最大), 所以优先级最高)

, 把堆顶数据和最后一个结点数据交换, 然后对交换后的对顶元素向下调整, 直到整棵树都变成小根堆





⚠️那么剩最后一个下标为8的结点怎么办呢, 别忘了 usedSize 是用来记录优先级队列中的长度的, 在优先级队列中删除数据之后, usedSize自减一次, 即代表堆中有效数据减少一个

回顾一下向下调整的代码, 每一个结点向下调整的限制是 child 下标值< len

清楚了堆的创建, 插入和删除, 实现优先级队列的插入和删除就很简单了

2, 实现优先级队列

2.1, offer – 插入数据

老规矩, 插入前先判满❗️, 如果满了要扩容

插入之后 usedSize要自加一次

    public void offer(int val) {
        if(isFull()) {
            //扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;//11
        //向上调整
        shiftUp(usedSize-1);//10
    }
    public boolean isFull() {
        return usedSize == elem.length;
    }

2.1, poll – 删除数据

老规矩, 删除前要先判空❗️, 如果为空, 不能继续删除

public void pop() {
        if(isEmpty()) {
            return;
        }
        swap(elem,0,usedSize-1);
        usedSize--;
        shiftDown(0,usedSize);
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }
    
    private void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

三、Java提供的PriorityQueue

1, PriorityQueue说明

PriorityQueue 实现了 Queue 这个接口

⚠️⚠️⚠️注意事项:

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

2️⃣不能插入 null 对象，否则会抛出 NullPointerException❗️❗️

因为PriorityQueue 中插入删除的数据是泛型类, 可以是基本类型对应的包装类, 也可以是自定义类, 在向上调整和向下调整的过程中, 需要不断地比较, 如果数据没有指定比较规则, 或者为null时, 程序就会抛出异常

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

任意多个是相对来说的, 类类型的数据存放在堆中, 所以数据个数最多不能超过堆的内存大小, 链表同理

4️⃣插入和删除元素的时间复杂度为 O(log₂N)

2, 使用PriorityQueue

2.1, PriorityQueue实例化方式

👉无参构造法 底层数组默认容量是

11


        Queue<Integer> priorityQueue1 = new PriorityQueue<>();

👉整形数据作为参数, 设置化底层数组容量

        Queue<Integer> priorityQueue2 = new PriorityQueue<>(10);

👉比较器(匿名内部类对象)作为参数传参, 设置push方法中的

向上调整时两数据比较规则


        Queue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

Java集合中的 PriorityQueue 底层的堆默认是小根堆, 如果要设置大根堆, 就必须传入比较器, 并重写 compare 方法, 如上代码所示

2.2, PriorityQueue常用方法

在 main 方法中展示使用方式：

        Queue<Integer> priorityQueue = new PriorityQueue<>();
        int[] array = {1,3,2,6,5,7,8,9,10,0};
        for(int x : array) {
            // 1, 插入数据
            priorityQueue.offer(x);
        }
        // 2,获取优先级最高的数据
        int ret1 = priorityQueue.peek();
        System.out.println("获取优先级最高的数据:" + ret1);

        // 3,删除优先级最高的数据
        int ret2 = priorityQueue.poll();
        System.out.println("删除优先级最高的数据:" + ret2);

        // 4,获取优先级队列中数据个数
        int size = priorityQueue.size();
        System.out.println("数据个数:" + size);

        // 5, 清空优先级队列
        priorityQueue.clear();

        // 6, 查看队列是否为空
        boolean bl = priorityQueue.isEmpty();
        System.out.println("队列是否为空:" + bl);
    }

运行结果:

总结

以上就是今天分享的关于数据结构中【优先级队列】的内容

一方面介绍了如何模拟实现简易的优先级队列以及(小根堆)堆的实现方式，一方面介绍了Java集合框架中的【PriorityQueue】类的基本使用

📃📃📃思考分析:

堆中的向下调整和向上调整有什么区别? 建堆为什么需要自下而上的向下调整,以及删除堆顶数据需要向下调整, 而插入数据需要向上调整?

🖋️🖋️🖋️

以小根堆为例:

1️⃣向下调整是父节点和左右孩子结点比较, 向上调整是当前结点和父结点比较, 向下调整和向上调整都是为了把小的数据往堆顶移动, 大的数据往堆底移动

2️⃣建堆的过程中

自下而上是为了

从”下面”出发, 不断的把目前最小的数据网上移动,

每次都需要向下调整是为了

保证最小数据移动到堆顶的同时, 左右子树也要保持小根堆

删除数据的过程中, 由于要让优先级最高的数据出队, 所以要舍弃堆顶, 和末尾数据交换后向下调整 , 重建小根堆

插入数据的过程中, 每次在末尾入队一个数据, 它没有左右子树, 不可能向下调整, 只能不断和父结点比较, 寻找这个新结点的合适位置

如果本篇对你有帮助，请点赞收藏支持一下，小手一抖就是对作者莫大的鼓励啦🤪🤪🤪

上山总比下山辛苦

下篇文章见