JDK源码之PriorityQueue解析

一.优先队列的应用

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

二.优先队列的实现原理

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

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

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

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

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

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

代码运行到这里，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出循环。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。

# JDK  # PriorityQueue  # 解决java 查看JDK中底层源码的实现方法  # 解决调试JDK源码时  # 不能查看变量的值问题  # 通过JDK源码角度分析Long类详解  # jdk源码阅读Collection详解  # 通过JDK源码分析关闭钩子详解  # 通过JDK源码学习InputStream详解  # Java从JDK源码角度对Object进行实例分析  # JDK源码中一些实用的“小技巧”总结  # 第一个  # 自己的  # 我们可以  # 操作系统  # 被称为  # 较小  # 则将  # 为空  # 的是  # 如果您  # 在这里  # 最好的  # 较高  # 数据结构  # 屡见不鲜  # 也很  # 第二个  # 并将  # 做一个  # 两条 

相关文章： 交易网站制作流程,我想开通一个网站，注册一个交易网址，需要那些手续？  网站微信制作软件,如何制作微信链接？  如何在局域网内绑定自建网站域名？  如何处理“XML格式不正确”错误 常见XML well-formed问题解决方法  建站之星安装需要哪些步骤及注意事项？  ,巨量百应是干嘛的？  如何选择靠谱的建站公司加盟品牌？  网站制作企业,网站的banner和导航栏是指什么？  魔方云NAT建站如何实现端口转发？  如何用手机制作网站和网页,手机移动端的网站能制作成中英双语的吗？  开源网站制作软件,开源网站什么意思？  javascript中对象的定义、使用以及对象和原型链操作小结  武汉网站如何制作,黄黄高铁武穴北站途经哪些村庄？  建站之星好吗？新手能否轻松上手建站？  如何快速搭建高效服务器建站系统？  如何选择香港主机高效搭建外贸独立站？  盘锦网站制作公司,盘锦大洼有多少5G网站？  广东专业制作网站有哪些,广东省能源集团有限公司官网？  美食网站链接制作教程视频,哪个教做美食的网站比较专业点？  如何安全更换建站之星模板并保留数据？  如何在橙子建站中快速调整背景颜色？  网站制作费用多少钱,一个网站的运营，需要哪些费用？  建站之星北京办公室：智能建站系统与小程序生成方案解析  平台云上自主建站：模板化设计与智能工具打造高效网站  如何通过商城免费建站系统源码自定义网站主题？  制作网站外包平台,自动化接单网站有哪些？  建站之星后台密码遗忘如何找回？  香港服务器如何优化才能显著提升网站加载速度？  制作宣传网站的软件,小红书可以宣传网站吗？  建站主机助手选型指南：2025年热门推荐与高效部署技巧  网站制作免费,什么网站能看正片电影？  怎么制作一个起泡网,水泡粪全漏粪育肥舍冬季氨气超过25ppm，可以有哪些措施降低舍内氨气水平？  如何快速上传自定义模板至建站之星？  建站168自助建站系统：快速模板定制与SEO优化指南  如何在搬瓦工VPS快速搭建网站？  做企业网站制作流程,企业网站制作基本流程有哪些？  高防服务器租用如何选择配置与防御等级？  制作表格网站有哪些,线上表格怎么弄？  网站制作中优化长尾关键字挖掘的技巧,建一个视频网站需要多少钱？  济南专业网站制作公司,济南信息工程学校怎么样？  如何在宝塔面板中修改默认建站目录？  mc皮肤壁纸制作器,苹果平板怎么设置自己想要的壁纸我的世界？  怀化网站制作公司,怀化新生儿上户网上办理流程？  西安专业网站制作公司有哪些,陕西省建行官方网站？  猪八戒网站制作视频,开发一个猪八戒网站，大约需要多少？或者自己请程序员，需要什么程序员，多少程序员能完成？  如何在云指建站中生成FTP站点？  5种Android数据存储方式汇总  建站之星免费模板：自助建站系统与智能响应式一键生成  ,石家庄四十八中学官网？  PHP 500报错的快速解决方法