4.1 手写Java PriorityQueue 核心源码

九路 等级 863 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 核心源码

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

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

收藏
评论区

相关推荐

4.1 手写Java PriorityQueue 核心源码
本章先讲解优先级队列和二叉堆的结构。下一篇代码实现 从一个需求开始 假设有这样一个需求:在一个子线程中,不停的从一个队列中取出一个任务,执行这个任务,直到这个任务处理完毕,再取出下一个任务,再执行。 其实和 Android 的 Handler 机制中的 Looper 不停的从 MessageQueue 中取出一个消息然后处理是一样的。 不过这个需
4.2 手写Java PriorityQueue 核心源码
上一节介绍了PriorityQueue的原理,先来简单的回顾一下 PriorityQueue 的原理 以最大堆为例来介绍 1. PriorityQueue是用一棵完全二叉树实现的。 2. 不但是棵完全二叉树,而且树中的每个根节点都比它的左右两个孩子节点元素大 3. PriorityQueue底层是用数组来保存这棵完全二叉树的。 如下图,是一棵最大堆。
JAVA 基本类型与 引用类型区别
 栈与堆都是Java用来在Ram中存放数据的地方。与C++不同,Java自动管理栈和堆,程序员不能直接地设置栈或堆。         Java的堆是一个运行时数据区,类的(对象从中分配空间。这些对象通过new、newarray、anewarray和 multianewarray等指令建立, 它们不需要程序代码来显式的释放。堆是由垃圾回收来负责的,堆的
JDK核心JAVA源码解析(4)
想写这个系列很久了,对自己也是个总结与提高。原来在学JAVA时,那些JAVA入门书籍会告诉你一些规律还有法则,但是用的时候我们一般很难想起来,因为我们用的少并且不知道为什么。知其所以然方能印象深刻并学以致用。 本篇文章针对堆外内存与DirectBuffer进行深入分析,了解Java对于堆外内存处理的机制,为下一篇文件IO做好准备 Java堆栈内存与堆外内
Java Collection
总结 == 1. 优先队列的作用是能保证每次取出的元素都是队列中权值最小的(Java的优先队列每次取最小元素,C++的优先队列每次取最大元素)。这里牵涉到了大小关系,元素大小的评判可以通过元素本身的自然顺序(_natural ordering_),也可以通过构造时传入的比较器(_Comparator_,类似于C++的仿函数)。 2. Java中Prio
Java堆,方法区,Java栈和本地方法栈浅析
最近在看《深入理解Java虚拟机》,书中给了几个例子,比较好的说明了几种OOM(OutOfMemory)产生的过程,大部分的程序员在写程序时不会太关注Java运行时数据区域的结构: ![](http://static.oschina.net/uploads/img/201611/04115646_t6Rm.gif) 感觉有必要通过几个实在的例子来加深对这
Java虚拟机堆内存(新生代)
Java中的堆是JVM所管理的最大的一块内存空间,主要用于存放各种类的实例对象。 在Java中,堆被划分成两个不同的区域:新生代,老年代。新生代又被分为了三个区域:Eden,from  survivor,to survivor。这样划分的目的是为了使JVM能够更好的管理堆内存中的对象,包括内存分配以及回收。 堆的内存模型大致为: 从图中可以看出: 堆大
java优先队列PriorityQueue修改队列内元素排序问题
* 今天发现了新大陆。我以前一直以为,PriorityQueue队列是基于堆排序的`不断更新排序`的,没错,它是不断更新排序的。但是前提是要`插入(删除)数据`,如果仅仅是修改已经稳定队列的值或内容,而不进行插入或者删除,那么,这个顺序是`不会变`的。 举个例子: import java.util.Comparator; i
java堆排序(大根堆)
实现堆排序的算法思路是先创建堆,也就是从叶子节点起对每一层的孩子节点及其对应位置的父亲节点进行比较,较大的孩子节点替换较小的父亲节点,一级一级比较替换,就创建出了大根堆,小根堆反之。创建好大根堆以后,我们,将整棵树的根节点与最后最后一个节点替换位置,然后去除最后一个节点,在创建一个新的大根堆,以此类推,完成排序。代码如下: /\*\* \* <p>堆排
JVM 面试
1、内存模型以及分区,需要详细到每个区放什么。 通俗的说, Java 虚拟机具有一个堆,堆是运行时数据区域,所有类实例和数组的内存均从此处分配。 JVM主要管理两种类型内存:堆和非堆,堆内存(Heap Memory)是在 Java 虚拟机启动时创建,非堆内存(Non-heap Memory)是在JVM堆之外的内存。 简单来说,堆是Java代码可及的内
JVM堆栈
栈与堆都是Java用来在Ram中存放数据的地方。与C++不同,Java自动管理栈和堆,程序员不能直接地设置栈或堆。 **堆内存用来存放由 new 创建的对象和数组。****在堆中分配的内存,由 Java 虚拟机的自动垃圾回收器来管理。** **栈的优势是,存取速度比堆要快,仅次于寄存器,****栈数据可以共享****。但缺点是,存在栈中的数据大小与生存
JVM系列之:内存与垃圾回收篇(二)
JVM系列之:内存与垃圾回收篇(二) ================== ##本篇内容概述: 1、堆Heap Area 2、方法区Method Area 3、运行时数据区总结 4、对象的实例化内存布局和访问定位 一、堆 Heap Area ------------- ### 1、堆的核心概念
JVM调优之jstack找出最耗cpu的线程并定位代码
jstack可以定位到线程堆栈,根据堆栈信息我们可以定位到具体代码,所以它在JVM性能调优中使用得非常多。下面我们来一个实例找出某个Java进程中最耗费CPU的Java线程并定位堆栈信息,用到的命令有ps、top、printf、jstack、grep。 第一步先找出Java进程ID,服务器上的Java应用名称为mrf-center: root@u
PriorityBlockingQueue深度解析(好文)
本文引自:[https://www.cnblogs.com/Elliott-Su-Faith-change-our-life/p/7472265.html](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fwww.cnblogs.com%2FElliott-Su-Faith-change-o
Tomcat中JVM内存溢出及合理配置
Tomcat本身不能直接在计算机上运行,需要依赖于硬件基础之上的操作系统和一个Java虚拟机。Tomcat的内存溢出本质就是JVM内存溢出,所以在本文开始时,应该先对Java JVM有关内存方面的知识进行详细介绍。 **一、Java JVM内存介绍** JVM管理两种类型的内存,堆和非堆。按照官方的说法:“Java 虚拟机具有一个堆,堆是运行时数据区域,