4.2 手写Java PriorityQueue 核心源码

九路 等级 1056 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底层是用数组来保存这棵完全二叉树的。 如下图,是一棵最大堆。
JDK源码分析
概述 前文「[JDK源码分析-PriorityQueue](https://www.oschina.net/action/GoToLink?url=http%3A%2F%2Fmp.weixin.qq.com%2Fs%3F__biz%3DMzU4NzYyMDE4MQ%3D%3D%26mid%3D2247483966%26idx%3D1%26sn%3D
Java Collection
总结 == 1. 优先队列的作用是能保证每次取出的元素都是队列中权值最小的(Java的优先队列每次取最小元素,C++的优先队列每次取最大元素)。这里牵涉到了大小关系,元素大小的评判可以通过元素本身的自然顺序(_natural ordering_),也可以通过构造时传入的比较器(_Comparator_,类似于C++的仿函数)。 2. Java中Prio
Java面向对象技术
问题及答案来源自《Java程序员面试笔试宝典》第四章 Java基础知识 4.2面向对象技术 **1、面向对象与面向过程有什么区别?** **看下面一个实例即可:** **面向过程就是分析出解决问题所需要的步骤,然后用函数把这些步骤一步一步实现,使用的时候依次调用;** **面向对象是把构成问题事务分解成各个对象,建立对象的目的不是为了完成一个步骤,而
java优先队列PriorityQueue修改队列内元素排序问题
* 今天发现了新大陆。我以前一直以为,PriorityQueue队列是基于堆排序的`不断更新排序`的,没错,它是不断更新排序的。但是前提是要`插入(删除)数据`,如果仅仅是修改已经稳定队列的值或内容,而不进行插入或者删除,那么,这个顺序是`不会变`的。 举个例子: import java.util.Comparator; i
ASMSupport教程4.2
<h2>4.2 生成Return操作</h2> <p>这一节我们将讲述如何生成return操作,我们将生成如下代码:</p> <div style="padding-bottom: 0px; margin: 0px; padding-left: 0px; padding-right: 0px; display: inline; float: none; pa
ClickHouse20.3 安装
1、检查环境 ====== 1.1、linux版本 ----------- [root@localhost ~]# cat /etc/redhat-release CentOS Linux release 7.7.1908 (Core) 1.2、SSE 4.2 ----------- [root@localhost
Eclipse 新建Servlet出错问题
      作为Java Web的新手,总是会遇到各种各样的问题.最近我在《Java Web整合开发王者归来JSP+Servlet+Struts+Hibernate+Spring》的指导下学习Java Web就碰到了新建servlet总是显示错误的问题: (我的环境:Eclipse 4.2,Tomcat 7) ![eclipse显示的错误](http:/
Idea破解
Idea破解 ====== Idea企业版解压版 ideaIU-2018.3.4.win JetbrainsIdesCrack-4.2-release.jar 破解步骤 ---- 一、JetbrainsIdesCrack-4.2-release.jar ,通常放入 $IDEA\_HOME/bin 目录下。 二、修改
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
PriorityQueue和PriorityBlockingQueue
点击**上方的****蓝字**关注我吧 _程序那些事_ **简介** Queue一般来说都是FIFO的,当然之前我们也介绍过Deque可以做为栈来使用。今天我们介绍一种PriorityQueue,可以按照对象的自然顺序或者自定义顺序在Queue中进行排序。 **PriorityQueue** 先看PriorityQueue,这个Qu
PythonStudy——线程中的几种消息队列
Queue ===== from queue import Queue,LifoQueue,PriorityQueue # 队列模块 queue # 类 Queue # 类 LifoQueue # 类 PriorityQueue # 与进程中的JoinableQueue 使用方式完全一样
Spring Framework 4.2 中的新功能和增强功能
本文同不至[http://www.waylau.com/new-features-and-enhancements-in-spring-framework-4.2/](https://www.oschina.net/action/GoToLink?url=http%3A%2F%2Fwww.waylau.com%2Fnew-features-and-enhan