4.1 手写Java PriorityQueue 核心源码

九路 等级 538 1 0

本章先讲解优先级队列和二叉堆的结构。下一篇代码实现

从一个需求开始

假设有这样一个需求:在一个子线程中,不停的从一个队列中取出一个任务,执行这个任务,直到这个任务处理完毕,再取出下一个任务,再执行。

其实和 Android 的 Handler 机制中的 Looper 不停的从 MessageQueue 中取出一个消息然后处理是一样的。

不过这个需求还有一点。需要我们的任务是有优先之分的,优先高的先执行,优先级低的后执行。比如现在队列中已经有了10个任务了,现在有一个紧急的任务需要处理,怎么办?

解决办法有多种:

  1. 用数组实现,把任务放到数组里面,每次任务入队后,根据任务的优先级排序,把优先级最大的排到最前面,取任务的时候从队头取
  2. 用链表实现,每次入队的时候把每个元素的优先级比较一下,把优先级最大的放链表尾部,取的尾部,取任务的时候每次都从尾部取就行了。

总结:上面两种方法都可以实现,不过都有一定的缺点

  • 第一种方法,用数组实现,入队的时候,需要遍历整个数组,才能找到合适的位置

入队的时间复杂度是O(n),出队的时间复杂度是O(1)

  • 第二种方法,用链表实现,和数组一样,也是需要遍历整个链表,才能找到合适的位置,入队的时间复杂度是O(n),出队的时间复杂度是O(1)

虽然出队效率很高,但是入队效率太低。有没有一种方法入队出队效率都很高呢? 当然有,就是Java 给我们提供了一个 PriorityQueue 也就是优先级队列 我们来看一下PriorityQueue的用法

PriorityQueue的用法

我们有一个任务类,在里面执行一些操作。如下:

/**
 *  我们的任务类
 */
public class Task {
    //任务的名称
    public String name;

    //优先级,是一个整数,我们规定,数越大优先级越高
    public int priority;


    public Task(String name,int priority){
        this.name = name;
        this.priority = priority;
    }

    //假如这是任务需要做的事
    public void doSomthing(){
        System.out.println("do somthing");
    }

    @Override
    public String toString() {
        return "taskName=" + name + " taskPriority=" + priority;
    }
}

测试代码如下:

  public static void main(String[] args){

        //比较两个任务,从大到小排序
        Comparator<Task> comparator = new Comparator<Task>() {
            @Override
            public int compare(Task o1, Task o2) {
                if(o1.priority > o2.priority){
                    return -1;
                }else if(o1.priority == o2.priority){
                    return 0;
                }else {
                    return 1;
                }
            }
        };

        //新建一个任务
        Queue<Task> priorityQueue =  new PriorityQueue<Task>(10,comparator);

        //新建了4个不同优先级的任务入队,数越大优先级越大,也最先执行
        priorityQueue.add(new Task("task1",23));
        priorityQueue.add(new Task("task2",34));
        priorityQueue.add(new Task("task3",15));
        priorityQueue.add(new Task("task4",79));

        //分别取出任务,然后打印
        System.out.println(priorityQueue.poll());   // 首先应该是 task4, 先取出来,因为优先级最大
        System.out.println(priorityQueue.poll());   // 然后才是   task2   被取出来
        System.out.println(priorityQueue.poll());   // 然后才是   task1   被取出来
        System.out.println(priorityQueue.poll());   // 最后才是   task3   被取出来,因为优先级最小
    }

输出如下:

taskName=task4 taskPriority=79
taskName=task2 taskPriority=34
taskName=task1 taskPriority=23
taskName=task3 taskPriority=15

由此可知,虽然入队的顺序是不一样的,但是出队的顺序,是优先大的先出队 如果现在有一个紧急的任务需要优先处理,那么就可以设置这个任务的优先级比79大, 就可以排到最前面,等到下一次从队列中取任务的时候,这个紧急的任务就被取出来了。

这就是优先级队列的作用。

PriorityQueue队列的原理

直接上结论:

  1. PriorityQueue是一个最大堆(或者用最小堆也是一样)
  2. 堆一种完全二叉树
  3. PriorityQueue是用一个数组存放二叉树中的元素的。

1 什么是完全二叉树?

完全二叉树:若设二叉树的深度为h,除第 h 层外,其它各层 (1 ~ h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

定义太抽象,我们上图来描述什么是二叉树。

4.1 手写Java PriorityQueue 核心源码

上由图可知:二叉树节点节点都在最左边。这就是完全二叉树,形态要记牢哦。

2 什么是堆结构?

堆结构有最大堆和最小堆,这里我们以最大堆为例。(最大堆懂了,那么最小堆自然就懂了)。 最大堆定义: 最大堆是一个完全二叉树,并且根节点的数都比左右两个节点的数大。

说白了就是最大的节点作用根。 由定义可知,最大堆有 2 个性质

  1. 最大堆是一个完全二叉树
  2. 最大堆,根节点比左右两个子节点大

如下图,是一个最大堆: 4.1 手写Java PriorityQueue 核心源码

上图是一个最大堆,首先是一棵完全二叉树,并且每个根节点都大于它的左右子节点

这就是最大堆结构,当然最小堆和最大堆是反着的,根节点比左右子节点要小。 最大堆的形态要记牢哦。

最大堆和优先级队列

由上图最大堆可知:

  1. 假如取元素的时候,只取整棵树的根节点,也就是 100 那个节点。也就是优先级最高的节点。
  2. 100 节点取走以后,我们只需要把剩下的节点中,找个最大的,放在根节点位置,
  3. 插入一个节点的时候,我们保证插入的节点放在适合的位置,满足二叉堆的性质即可。

那么这样的数据结构不就是优先级队列吗。 现在的问题就是

  1. 如何用数组来存放二叉堆结构?(上面说了,二叉堆是用数组来存放数据的)
  2. 如何向二叉堆中插入一个节点,并放到合适的位置上?
  3. 取出根节点后,怎么找到剩下的最大的节点并放到合适的位置上?

下面我们来一一解决上面三个问题

1 如何用数组来存放二叉堆结构?

我们以下图一个简单的二叉堆为例

4.1 手写Java PriorityQueue 核心源码

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

索引为0的位置不用。从1开始,为了方便后面计算。

对照图这两副图可以知道,二叉堆中的元素分层存放到数组中(从索引1开始存放) 有下面几个性质: 1 对于一个索引为n的节点,它的左孩子的索引是 2*n ,它的右孩子索引是2*n+1

比如 索引为2的节点是19

  1. 那么它的左孩子是 2 * 2 是数组中的索引为4的位置 ,也就是16
  2. 它的右孩子是 2*2 + 1 是数组中的索引为5的位置,也就是9

同样也可以由节点的索引,知道此节点的父节点的索引。 比如 索引为2的节点是19 那么它的父节点是 2 / 2 ,也就是索引为1的位置 比如 索引为3的节点是28 那么它的父节点是 3 / 2 ,也是 1 ,是和图中能对得上吧。

由此可知:用数组存放二叉堆(从索引为1开始),有以下两个性质: 对于索引为 n 的节点

  1. 找孩子节点:左孩子的索引是 2*n ,右孩子的索引是 2*n + 1
  2. 找父节点: 父节点的索引是 n/2

注:只有完全二叉树按层序存放到数组中才有这样的性质。必须是完全二叉树,必须是完全二叉树,必须是完全二叉树。重要的事情说三遍

2 如何向二叉堆中插入一个节点,并放到合适的位置上?

要向二叉堆中插入一个节点,插入节点后 只需要满足是完全二叉树并且任意一个根节点都比它的左右两个孩子的大就行了。

感觉说的是废话 如下图,我们要向二叉堆中插入一个节点为 30 的元素。 4.1 手写Java PriorityQueue 核心源码

  1. 第一步:新来的节点放到数组的最后的位置 也就是索引为 6 的位置(数组大小不够了就扩容,后面讲)
  2. 第二步:不停的与自己的父节点比大小,比父节点大,就交换位置 然后重复以上步骤

经过上面两步,就可以将一个节点插入到合适的位置上了。如下图 4.1 手写Java PriorityQueue 核心源码

知道了如何向二叉堆中插入一个节点,,那么如何取出根节点后,怎么找到剩下的最大的节点并放到合适的位置上?也就是删除根节点后,剩下的怎么办呢?

3 如何删除根节点?

删除根节点很容易,关键是删除后剩下的节点怎么摆放?如下图 4.1 手写Java PriorityQueue 核心源码

把根节点100删除后

  1. 第一步:把最后一个节点9放到100的位置上,也就是索引为 1 的位置上。
  2. 第二步:从根节点开始,不停的与它的左右两上节点比大小,找到左右两个节点为中的比较大的节点,然后交换位置,以此类推,直到这个节点比它的左右两个节点都大为止

如下图,第一步: 4.1 手写Java PriorityQueue 核心源码

第二步:找出根节点9的最大的孩子节点 ,也就是 28,然后交换位置 :如下图

4.1 手写Java PriorityQueue 核心源码

直到没有孩子可以比较了或者说有孩子,但是比孩子的节点要大,便不再比较

由上面可以知道,插入和删除都有了,下一章节就是代码实现了

收藏
评论区

相关推荐

1 手写ArrayList核心源码
手写ArrayList核心源码 ArrayList是Java中常用的数据结构,不光有ArrayList,还有LinkedList,HashMap,LinkedHashMap,HashSet,Queue,PriorityQueue等等,我们将手写这些常用的数据结构的核心源码,用尽量少的代码来揭示核心原理。 下面我们来手写ArrayList的核心源码 首先
JVM--虚拟机方法调用
概述 Java能做到一次编译,随处运行,最要是归功于java虚拟机 和class文件,我们知道,计算机是0和1 的世界,并且只认0和1,所以不管是什么语言什么编译类型,最终给计算机的都是0和1,java也不例外,但是我们的java编译成了class文件,class怎么就转换成0和1了呢,或者说机器码呢?其实这一步是虚拟机帮我们干的。当然,虚拟机是建立在不同
4.1 手写Java PriorityQueue 核心源码
本章先讲解优先级队列和二叉堆的结构。下一篇代码实现 从一个需求开始 假设有这样一个需求:在一个子线程中,不停的从一个队列中取出一个任务,执行这个任务,直到这个任务处理完毕,再取出下一个任务,再执行。 其实和 Android 的 Handler 机制中的 Looper 不停的从 MessageQueue 中取出一个消息然后处理是一样的。 不过这个需
4.2 手写Java PriorityQueue 核心源码
上一节介绍了PriorityQueue的原理,先来简单的回顾一下 PriorityQueue 的原理 以最大堆为例来介绍 1. PriorityQueue是用一棵完全二叉树实现的。 2. 不但是棵完全二叉树,而且树中的每个根节点都比它的左右两个孩子节点元素大 3. PriorityQueue底层是用数组来保存这棵完全二叉树的。 如下图,是一棵最大堆。
.NET C#到Java没那么难,MVC篇
.NET C到Java没那么难,MVC篇 .NET C到Java没那么难,MVC篇 最典型的JAVA MVC就是JSP servlet javabean的模式。比较好的MVC,老牌的有Struts、
Groovy初探
开始之前 了解本教程的主要内容,以及如何从中获得最大收获。 关于本教程 如果现在有人要开始完全重写 Java,那么 Groovy 就像是 Java 2.0。Groovy 并没有取代 Java,而是作为 Java 的补充,它提供了更简单、更灵活的语法,可以在运行时动态地进行类型检查。您可以使用 Groovy 随意编写 Java 应用程序,连接 Java
如何用 JS 实现二叉堆
这是第 90 篇不掺水的原创,想获取更多原创好文,请搜索公众号关注我们吧 本文首发于政采云前端博客:如何用 JS 实现二叉堆(https://zoo.team/ar
synchronized锁升级过程
1.前置知识:    1.1 JAVA对象的内存布局            hotspot虚拟机中,普通对象在堆中的存储可以划分成三部分:对象头(包含了MarkWord和类型指针)、实例例数据和padding。JAVA对象的内存布局MarkWord的长度为4byte/8byte,用于存储对象自身的运行时数据
一篇文章帮你搞懂二叉堆的那些事
【系列文章推荐阅读】 1. 什么是二叉堆?“二叉”自不必多说,本章主要介绍的树都是二叉树。那么啥是“堆”呢?我们在日常生活中,通常会说“一堆东西”或者“堆东西”,这里的“堆”,通常指重叠放置的许多东西。我们在堆东西的时候,肯定都有一个经验,即:为了使这堆东西更稳定,会将比较重的、大的东西放在下面,比较轻的、小的东西放在上面。这个经验放在数据结
从未有人把JVM原理讲的这么详细
JVM原理1.简述JVM是Java Virtual Machine(Java虚拟机)的缩写,是通过在实际的计算机上仿真模拟各种计算机功能来实现的。由一套字节码指令集、一组寄存器、一个栈、一个垃圾回收堆和一个存储方法域等组成。JVM屏蔽了与操作系统平台相关的信息,使得Java程序只需要生成在Java虚拟机上运行的目标代码(字节码),就可在多种平台上不加修改的运
一篇文章通俗易懂的让你彻底理解 Java 注解
很多Java程序员,对Java的注解一知半解,更有甚者,有的人可能连注解是什么都不知道本文我们用最简单的 demo , 最通俗最短的语言,带你了解注解到底是什么?先来简单回顾一下基础,我们知道,Java 的源文件编辑后,生成 .class 文件,1. .Java源文件,这个是源文件时期2. 源文件经过编译生成 .class 字节码文件,这个也是编译时期3
秋招已经开始准备了!【Java面试题】最新Java开发岗面试知识笔记
在最近两个月不断的面试中,我分类总结了 Java 开发岗位面试中的一些知识点。主要包括以下几个部分: 1. Java 基础知识点 2. Java 常见集合 3. 高并发编程(JUC 包) 4. JVM 内存管理 5. Java 8 知识点 6. 网络协议相关 7. 数据库相关 8. MVC 框架相关 9. 大数据相关 10. Linux 命令相关面试,
阿里Java架构师谈:2021年最新Java面试经历
第一家是美团美团的话,三面下来,设计的内容知识也是挺广的吧,有MySQL、Redis、Kafka、线程、算法、+、volatile、线程、并发、设计模式等等... 一面问题:MySQL+Redis+Kafka+线程+算法 mysql知道哪些存储引擎,它们的区别 mysql索引在什么情况下会失效 mysql在项目中的优化场景,慢查询解决等 my
C进阶 - 内存四驱模型
一.内存四驱模型不知我们是否有读过 《深入理解 java 虚拟机》这本书,强烈推荐读一下。在 java 中我们将运行时数据,分为五个区域分别是:程序计数器,java 虚拟机栈,本地方法栈,java 堆,方法区。在 c/c++ 中我们将运行时数据,分为四个区域分别是:栈区,堆区,数据区,代码区。我们详细来介绍下:1. 栈区:由编译器自动分配释放 ,存放函数的
一次性带你了解清楚Java内存模型!
[Java 内存模型]咳咳咳,能看完的都是人上人。。。。Java 虚拟机内部使用 JMM(Java 内存模型) 将内存划分为两个逻辑单元,线程栈(或者叫本地内存)和堆。每一个线程都有属于自己的线程栈,在线程栈中会保存局部变量(也叫做本地变量)、方法中定义的参数和异常处理器的参数(catch中的参数);这些参数和变量都属于线程局部操作,会被隔离,所以不受内存模