4.2 手写Java PriorityQueue 核心源码

九路 等级 732 0 0
标签: Java

上一节介绍了PriorityQueue的原理,先来简单的回顾一下 PriorityQueue 的原理

以最大堆为例来介绍

  1. PriorityQueue是用一棵完全二叉树实现的。
  2. 不但是棵完全二叉树,而且树中的每个根节点都比它的左右两个孩子节点元素大
  3. PriorityQueue底层是用数组来保存这棵完全二叉树的。

如下图,是一棵最大堆。 4.2 手写Java PriorityQueue 核心源码

最大堆的删除操作 删除指的是删除根元素,也就是图中的100元素 删除元素也就是 shiftDown 操作,向下翻 删除一个根元素有以下步骤:

  1. 将100元素删除,将最后一个元素12放到100的位置上,12成为根节点
  2. 找出 12 这个节点的左右两个孩子节点中的最大的,也就是图中的28节点
  3. 12 出 28节点进行比较,如果12比28小,则交换位置
  4. 12节点继续重复2,3步骤,直到12比它的左右孩子节点都大则停止

最大堆插入一个节点 插入一个节点,也叫shiftUp操作,向上翻 以插入一个节点23为例,步骤如下:

  1. 将23放到二叉树的最后位置,也就是成为了9这个节点的左孩子
  2. 23与它的父节点进行比较,如果比它的父节点大,就交换位置
  3. 23这个节点继续重要第2步骤,直到比它的父节点小方停止比较

代码实现 首先我们先上两张图 4.2 手写Java PriorityQueue 核心源码

我们从左往右,按层序遍历,分别存放到数组的相应索引对应的位置上。 数组的第0个索引位置我们不用,从索引为1的位置开始存放。 最终这个最大堆存放到数组中,如下图 4.2 手写Java PriorityQueue 核心源码

首先实现一个最简单的只存 int 类型的优先级队列 QPriorityQueueInt 完整代码如下:

//最大堆,只存放int,并且没有扩容机制
public class QPriorityQueueInt {
    //默认底层数据大小为10
    private static int DEFAULT_INIT_CAPACITY = 10;

    //底层数组
    private int[] queue;

    //节点的个数
    private int size;

    public QPriorityQueueInt() {
        //因为数组是从索引 1 的位置开始存放,索引为 0 的位置不用
        //所以开辟空间的时候需要加 1
        queue = new int[DEFAULT_INIT_CAPACITY + 1];

        //当前数组中节点的个数为0
        size = 0;
    }

    //返回节点的个数
    public int size() {
        return size;
    }

    //最大堆是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //添加一个节点
    public void add(int e) {
        //将元素存放到数组当前最后一个位置上
        queue[size + 1] = e;

        //个数需要加1
        size++;

        //需要向上翻
        shiftUp(size);
    }

    //向上翻,最大堆中的最后一个节点,不停的与父节点比较
    //最大堆中父节点的索引是 k / 2
    private void shiftUp(int k) {
        // k > 1 ,说明从第2个节点开始,因为如果只有一个节点的话,不需要比较了
        // queue[k] > queue[k / 2] ,当前节点大于父节点
        while (k > 1 && queue[k] > queue[k / 2]) {
            //交换位置
            swap(k, k / 2);

            //把父节点的索引赋值给 k,然后继续重复上面步骤
            k = k / 2;
        }
    }

    //删除最大堆中的节点
    public int poll() {

        //把第1个位置的节点保存起来
        int result = queue[1];

        //把最后一个节点放到第1个节点上面,成为整棵树的根节点
        queue[1] = queue[size];

        //别忘了size 要减1
        size--;

        //最后一个节点成为根节点后,就需要向下翻了
        //向下翻的目的就是把大的节点翻上来
        shiftDown(1);

        //返回第1个节点,也就是队头节点
        return result;
    }


    //向下翻
    private void shiftDown(int k) {
        //2 * k <= size ,2*k 是左孩子
        //2 * k <= size ,是当前节点有左孩子
        //至少有个左孩子才可以交换,因为是完全二叉树,左孩子没有,右孩子肯定没有
        while (2 * k <= size) {

            //比较左右两个孩子节点,将大的节点的索引赋值给 j

            //左孩子索引
            int j = 2 * k;
            //如果有右孩子,且 右孩子大于左孩子,将右孩子索引赋值给j
            if (j + 1 <= size && queue[j + 1] > queue[j]) {
                j = j + 1;
            }

            //现在 j 保存的是左右孩子中较大的节点的索引
            //比较当前节点和左右孩子中较大的节点
            //如果比左右孩子中较大的节点还大,则不用向下翻了
            if (queue[k] > queue[j]) {
                break;
            }

            //否则交换当前节点和左右孩子中较大的节点
            swap(k, j);

            //把左右孩子中较大的节点的索引赋值给k,继续向下翻
            k = j;
        }
    }

    //交换两个位置
    private void swap(int i, int j) {
        int t = queue[i];
        queue[i] = queue[j];
        queue[j] = t;
    }

}

下面是测试代码:

public static void main(String[] args) {
    QPriorityQueueInt queue = new QPriorityQueueInt();

    //随便弄5个数入队,数越大优先级越大
    //由于我们的QPriorityQueueInt默认只支持10个元素
    //所以插入的节点个数不要多于10个
    queue.add(3);
    queue.add(5);
    queue.add(1);
    queue.add(8);
    queue.add(7);

    //打印
    System.out.println(queue.poll());
    System.out.println(queue.poll());
    System.out.println(queue.poll());
    System.out.println(queue.poll());
    System.out.println(queue.poll());
}

输出如下:

8
7
5
3
1

从输出可以看出来,虽然7是最后入队的,但是优先级比较高,第二次就打印出来了。 优先级队列,同样是用数组实现。但是入队的效率比单纯的用数组排序要高多了。

至于扩容机制,读者可以自己查阅相关资源,自己实现。

收藏
评论区

相关推荐

1 手写ArrayList核心源码
手写ArrayList核心源码 ArrayList是Java中常用的数据结构,不光有ArrayList,还有LinkedList,HashMap,LinkedHashMap,HashSet,Queue,PriorityQueue等等,我们将手写这些常用的数据结构的核心源码,用尽量少的代码来揭示核心原理。 下面我们来手写ArrayList的核心源码 首先
4.1 手写Java PriorityQueue 核心源码
本章先讲解优先级队列和二叉堆的结构。下一篇代码实现 从一个需求开始 假设有这样一个需求:在一个子线程中,不停的从一个队列中取出一个任务,执行这个任务,直到这个任务处理完毕,再取出下一个任务,再执行。 其实和 Android 的 Handler 机制中的 Looper 不停的从 MessageQueue 中取出一个消息然后处理是一样的。 不过这个需
4.2 手写Java PriorityQueue 核心源码
上一节介绍了PriorityQueue的原理,先来简单的回顾一下 PriorityQueue 的原理 以最大堆为例来介绍 1. PriorityQueue是用一棵完全二叉树实现的。 2. 不但是棵完全二叉树,而且树中的每个根节点都比它的左右两个孩子节点元素大 3. PriorityQueue底层是用数组来保存这棵完全二叉树的。 如下图,是一棵最大堆。
1 Java内存区域与内存溢出异常
1 java虚拟机对内存的管理 java虚拟机在执行java程序的时候把内存分为若干个不同的区,这些区各自有不同的用处,以及创建和销毁时间. 有的区随着虚拟机的启动而启动,有的区则依赖用户线程的启动和结束而启动和结束. 根据java虚拟机规范,java虚拟机将内存分为下面几个部分:如下图 image(https://imghelloworld.o
.NET C#到Java没那么难,MVC篇
.NET C到Java没那么难,MVC篇 .NET C到Java没那么难,MVC篇 最典型的JAVA MVC就是JSP servlet javabean的模式。比较好的MVC,老牌的有Struts、
.NET C#到Java没那么难,Servlet篇
.NET C到Java没那么难,Servlet篇 .NET C到Java没那么难,Servlet篇 前言 .NET C到Java没那么难,都是面向对象的语言,而且语法还是相似的,先对比一下开发
Linux下安装jdk
一 、安装前 java 1.查看是否已安装JDK yum list installed |grep java 2.卸载CentOS系统Java环境 yum y remove java1.8.0openjdk 表示卸载所有openjdk相关文件输入 yum y remove tzdatajava.noarch 卸载t
Java中的浮点数四舍五入到小数点后2位的几种方法
前言 四舍五入到2或3个小数位是我们Java程序员日常开发中肯定会遇到。幸运的是,Java API提供了几种在Java中舍入数字的方法 我们可以使用Math.round(),BigDecimal或DecimalFormat将Java中的任何浮点数四舍五入到n个位置。我个人更喜欢使用BigDecimal在Java中四舍五入任何数字,因为它具有便捷的API并
Groovy初探
开始之前 了解本教程的主要内容,以及如何从中获得最大收获。 关于本教程 如果现在有人要开始完全重写 Java,那么 Groovy 就像是 Java 2.0。Groovy 并没有取代 Java,而是作为 Java 的补充,它提供了更简单、更灵活的语法,可以在运行时动态地进行类型检查。您可以使用 Groovy 随意编写 Java 应用程序,连接 Java
《java 核心技术》卷1 学习 概述 第一章Java程序设计概述
从浅面了解Java 1.Java 在语言得地位 现在有所下降 但仍是老大哥 所以值得学习 2.Java特性 1.简单性:从一方面来说 Java可以支持在小型机器上运行 必定不是很复杂得,所以上手不难 2.面向对象:Java有相比于其他的语言 更简单得接口
Java里面的十万个为什么
Java里面的十万个为什么 1.不是说 JVM 是运行 Java 程序的虚拟机吗?那 JRE 和 JVM 的关系是怎么样的呢?简单地说,JRE 包含 JVM 。JVM 是运行 Java 程序的核心虚拟机,而运行 Java 程序不仅需要核心虚拟机,还需要其他的类加载器,字节码校验器以及大量的基础类库。JRE 除包含 JVM 之外,还包含运行 Java 程序的其
Java学习路线
阶段一 (夯实基础)Java基础语法学习目标:1.熟悉Java等基本概念2.掌握Eclipse/IDEA集成开发工具的安装、配置和应用3.熟悉Java基本语法、基本类型、运算符和表达式4.掌握分支、循环逻辑语句、数组等知识的应用知识点列表:JDK、JRE、JVM基本概念Java环境搭建和配置安装和使用Eclipse/IDEA开发环境Java基本数据类型变量,
Java开发面试高频考点学习笔记(每日更新)
Java开发面试高频考点学习笔记(每日更新) 1.深拷贝和浅拷贝 2.接口和抽象类的区别 3.java的内存是怎么分配的 4.java中的泛型是什么?类型擦除是什么? 5.Java中的反射是什么 6.序列化与反序列化 7.Object有哪些方法? 8.JVM内存模型 9.类加载机制 10.对象的创建和对象的布局 11.Java的四种引用
2021年度最全面JVM虚拟机,类加载过程与类加载器
前言类装载器子系统是JVM中非常重要的部分,是学习JVM绕不开的一关。一般来说,Java 类的虚拟机使用 Java 方式如下:Java 源程序(.java 文件)在经过 Java 编译器编译之后就被转换成 Java 字节代码(.class 文件)。类加载器负责读取 Java 字节代码,并转换成 java.lang.Class类的一个实例。每个这样的实例用来表
2021年度最全面JVM虚拟机,类加载过程与类加载器
前言类装载器子系统是JVM中非常重要的部分,是学习JVM绕不开的一关。一般来说,Java 类的虚拟机使用 Java 方式如下:Java 源程序(.java 文件)在经过 Java 编译器编译之后就被转换成 Java 字节代码(.class 文件)。类加载器负责读取 Java 字节代码,并转换成 java.lang.Class类的一个实例。每个这样的实例用来表