JDK源码之PriorityQueue解析

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: JDK源码之PriorityQueue解析

这篇文章主要为大家详细介绍了JDK源码之PriorityQueue,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

一.优先队列的应用

优先队列在程序开发中屡见不鲜,比如操作系统在进行进程调度时一种可行的算法是使用优先队列,当一个新的进程被fork()出来后,首先将它放到队列的最后,而操作系统内部的Scheduler负责不断地从这个优先队列中取出优先级较高的进程执行;爬虫系统在执行时往往也需要从一个优先级队列中循环取出高优先级任务并进行抓取。可以想见,如果类似这样的任务不适用优先级进行划分的话,系统必会出现故障,例如操作系统中低优先级进程持续占用资源而高优先级进程始终在队列中等待。此外,优先队列在贪婪算法中也有一些应用。

二.优先队列的实现原理

优先队列的实现方式是使用二叉堆的结构,需要满足以下两条性质(Heap property),这里以小顶堆为例讲解:

  1.任何结点的值都小于或等于其子节点的值。
  2.所有结点从上到下,从左到右填入,即一棵完全二叉树。

基于这两条规律,二叉堆在实现中往往会使用一个数组,下面我们研究一下JDK中二叉堆(优先队列)的实现。

三.优先队列在JDK中的实现方式

研究源码最好的方式是debug,看每一步变量的变化,我们可以简单写一个Demo,debug进源码一探究竟:

图片.png

这里我们简单地创建一个优先队列,向其中添加三个元素,我们可以在代码第一行打一个断点,如果您使用Eclipse编辑器的话,接下来可以按F5进入源码中:

图片.png

代码运行到这里,PriorityQueue调用自己的一个重载构造器,第一个参数是数组默认大小,第二个是元素比较的Comparator,我们这里的Demo比较简单,您在使用优先队列时可以选择实现自己的Comparator。

public PriorityQueue(int initialCapacity,
            Comparator<? super E> comparator) {
   // Note: This restriction of at least one is not actually needed,
   // but continues for 1.5 compatibility
   if (initialCapacity < 1)
     throw new IllegalArgumentException();
   this.queue = new Object[initialCapacity];
   this.comparator = comparator;
 }

接下来我们研究一下添加元素时的offer操作:

public boolean offer(E e) {
   if (e == null)
     throw new NullPointerException();
   //记录了队列被修改的次数
   modCount++;
   int i = size;
   if (i >= queue.length)
     //扩容
     grow(i + 1);
   //增加元素个数
   size = i + 1;
   if (i == 0) 
     //第一次添加元素,直接放到第0个位置即可
     queue[0] = e;
   else
     //需要将元素放到最后,再做上滤操作
     siftUp(i, e);
   return true;
 }

我们逐行来解释一下,首先offer方法判断参数是否为空,不为空则对变量modCount自增,modCount记录了队列被修改的次数,接下来,判断数组是否会越界,如果越界则通过grow进行扩容,接下来添加元素,如果当前元素为0个则直接将元素放到数组第一个位置,否则做一个siftUp的操作。

private void grow(int minCapacity) {
   int oldCapacity = queue.length;
   // Double size if small; else grow by 50%
   int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                    (oldCapacity + 2) :
                    (oldCapacity >> 1));
   // overflow-conscious code
   if (newCapacity - MAX_ARRAY_SIZE > 0)
     newCapacity = hugeCapacity(minCapacity);
   //元素拷贝
   queue = Arrays.copyOf(queue, newCapacity);

上面的代码对队列扩容,源码中注释也很清晰,首先判断当前的数组大小是否足够小(<64),如果足够小则将大小扩充为2倍,否则将原大小加上50%。需要注意的是,这里最后做了一个大小是否溢出的判断。

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
      throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
      Integer.MAX_VALUE :
      MAX_ARRAY_SIZE;
  }

如果需要扩容的大小已经<0了,显然已经溢出了,在这里抛出了OutOfMemory的异常。

private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
      //计算父亲节点的下标
      int parent = (k - 1) >>> 1;
      Object e = queue[parent];
      //与父节点进行比较
      if (comparator.compare(x, (E) e) >= 0)
        break;
      queue[k] = e;
      k = parent;
    }
    queue[k] = x;
  }

为了保证优先队列的性质1,在插入每个元素时都需要与该节点父亲进行比较,找到其正确位置,有些数据结构书中,这个操作被称为上滤(percolate up)。

入队操作已经说完了,接下来是出队操作,即poll()操作:

public E poll() {
    if (size == 0)
      return null;
    int s = --size;
    //自增变量,代表队列修改次数
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
      siftDown(0, x);
    return result;
  }

这个方法首先将数组第一个元素作为结果,(因为如果是小顶堆的话堆顶始终是最小元素),并将队列的最后一个元素放到第一个位置,最后用siftDown做一些调整,保证队列的性质,这个操作被称为下滤(percolate down)。

private void siftDownUsingComparator(int k, E x) {
 
 
   int half = size >>> 1;
   //这里k必须有孩子,故叶节点需要比较
   while (k < half) {
     //以下几行代码到较小的那个儿子,用变量c表示
     int child = (k << 1) + 1;
     //这里假设左儿子比较小
     Object c = queue[child];
     int right = child + 1;
     //左右儿子比较,如果右儿子小则将c赋值为右儿子
     if (right < size &&
       comparator.compare((E) c, (E) queue[right]) > 0)
       c = queue[child = right];
     //如果x比小儿子还小,说明k就是正确位置
     if (comparator.compare(x, (E) c) <= 0)
       break;
     queue[k] = c;
     k = child;
   }
   queue[k] = x;
 }

如上图,下滤过程中k不断与其儿子进行比较,如果满足优先队列的顺序性,则break出循环。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持"java开发全栈"。

相关文章
|
1天前
|
存储 设计模式 算法
【23种设计模式·全精解析 | 行为型模式篇】11种行为型模式的结构概述、案例实现、优缺点、扩展对比、使用场景、源码解析
行为型模式用于描述程序在运行时复杂的流程控制,即描述多个类或对象之间怎样相互协作共同完成单个对象都无法单独完成的任务,它涉及算法与对象间职责的分配。行为型模式分为类行为模式和对象行为模式,前者采用继承机制来在类间分派行为,后者采用组合或聚合在对象间分配行为。由于组合关系或聚合关系比继承关系耦合度低,满足“合成复用原则”,所以对象行为模式比类行为模式具有更大的灵活性。 行为型模式分为: • 模板方法模式 • 策略模式 • 命令模式 • 职责链模式 • 状态模式 • 观察者模式 • 中介者模式 • 迭代器模式 • 访问者模式 • 备忘录模式 • 解释器模式
【23种设计模式·全精解析 | 行为型模式篇】11种行为型模式的结构概述、案例实现、优缺点、扩展对比、使用场景、源码解析
|
1天前
|
设计模式 存储 安全
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
结构型模式描述如何将类或对象按某种布局组成更大的结构。它分为类结构型模式和对象结构型模式,前者采用继承机制来组织接口和类,后者釆用组合或聚合来组合对象。由于组合关系或聚合关系比继承关系耦合度低,满足“合成复用原则”,所以对象结构型模式比类结构型模式具有更大的灵活性。 结构型模式分为以下 7 种: • 代理模式 • 适配器模式 • 装饰者模式 • 桥接模式 • 外观模式 • 组合模式 • 享元模式
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
|
1天前
|
设计模式 存储 安全
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
创建型模式的主要关注点是“怎样创建对象?”,它的主要特点是"将对象的创建与使用分离”。这样可以降低系统的耦合度,使用者不需要关注对象的创建细节。创建型模式分为5种:单例模式、工厂方法模式抽象工厂式、原型模式、建造者模式。
【23种设计模式·全精解析 | 创建型模式篇】5种创建型模式的结构概述、实现、优缺点、扩展、使用场景、源码解析
|
25天前
|
缓存 监控 Java
Java线程池提交任务流程底层源码与源码解析
【11月更文挑战第30天】嘿,各位技术爱好者们,今天咱们来聊聊Java线程池提交任务的底层源码与源码解析。作为一个资深的Java开发者,我相信你一定对线程池并不陌生。线程池作为并发编程中的一大利器,其重要性不言而喻。今天,我将以对话的方式,带你一步步深入线程池的奥秘,从概述到功能点,再到背景和业务点,最后到底层原理和示例,让你对线程池有一个全新的认识。
52 12
|
20天前
|
PyTorch Shell API
Ascend Extension for PyTorch的源码解析
本文介绍了Ascend对PyTorch代码的适配过程,包括源码下载、编译步骤及常见问题,详细解析了torch-npu编译后的文件结构和三种实现昇腾NPU算子调用的方式:通过torch的register方式、定义算子方式和API重定向映射方式。这对于开发者理解和使用Ascend平台上的PyTorch具有重要指导意义。
|
2天前
|
安全 搜索推荐 数据挖掘
陪玩系统源码开发流程解析,成品陪玩系统源码的优点
我们自主开发的多客陪玩系统源码,整合了市面上主流陪玩APP功能,支持二次开发。该系统适用于线上游戏陪玩、语音视频聊天、心理咨询等场景,提供用户注册管理、陪玩者资料库、预约匹配、实时通讯、支付结算、安全隐私保护、客户服务及数据分析等功能,打造综合性社交平台。随着互联网技术发展,陪玩系统正成为游戏爱好者的新宠,改变游戏体验并带来新的商业模式。
|
26天前
|
Java 编译器 API
深入解析:JDK与JVM的区别及联系
在Java开发和运行环境中,JDK(Java Development Kit)和JVM(Java Virtual Machine)是两个核心概念,它们在Java程序的开发、编译和运行过程中扮演着不同的角色。本文将深入解析JDK与JVM的区别及其内在联系,为Java开发者提供清晰的技术干货。
25 1
|
3月前
|
Java
安装JDK18没有JRE环境的解决办法
安装JDK18没有JRE环境的解决办法
381 3
|
1天前
|
NoSQL 关系型数据库 MySQL
Linux安装jdk、mysql、redis
Linux安装jdk、mysql、redis
39 7
|
4月前
|
Java 关系型数据库 MySQL
"解锁Java Web传奇之旅:从JDK1.8到Tomcat,再到MariaDB,一场跨越数据库的冒险安装盛宴,挑战你的技术极限!"
【8月更文挑战第19天】在Linux上搭建Java Web应用环境,需安装JDK 1.8、Tomcat及MariaDB。本指南详述了使用apt-get安装OpenJDK 1.8的方法,并验证其版本。接着下载与解压Tomcat至`/usr/local/`目录,并启动服务。最后,通过apt-get安装MariaDB,设置基本安全配置。完成这些步骤后,即可验证各组件的状态,为部署Java Web应用打下基础。
65 1

推荐镜像

更多