深入浅析JDK中的PriorityQueue-创新互联

深入浅析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;
  }