实例分析Java优先级队列的本质

优先队列（PriorityQueue），又称为优先级队列，是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。优先级队列的实现，往往是依靠堆数据结构，最大优先队列可以选用大堆，最小优先队列可以选用小堆来实现。

举一个很生动形象的例子：医院门诊中的一名医生接诊数名前来就诊的病人，通常按照流程来说，是采用先到先服务的顺序（FIFO）。但是如果病人中有人患有急性心脏病，那么显然这个病人需要得到优先治疗。也就说明这个病人的优先级别最高。在计算机系统中，绝大多数都支持多任务，这种多任务调度也类似于医院门诊。CPU相当于医生，计算任务相当于病人。每个任务都有一个优先级指标（priority），优先级高的任务可以被CPU优先处理。这种优先级别的机制在算法中，也有大量的应用。比如堆排序、霍夫曼编码等。

上面的各种情况实际上可以被归纳为这样一种模式：服务端（医生、CPU、霍夫曼算法…）通过一种叫call-by-priority（循优先级访问）的方式访问客户数据（病人，任务，待编码字符…），每个客户数据都有一个优先级指标。这种访问方式需要对应一种数据结构，可以记录、维护所有数据的优先级指标，并通过接口对这些数据进行操作。

优先级队列是很重要的一个Java的建立在无界优先级队列和优先级堆的API。PriorityQueue类实际上是一部分的java.util包，是一个通用的实现Java中的基于优先级的队列。Java API 在java.util包中具有通用接口名称Queue 。这是Java Collection Framework API的一部分，旨在在处理之前保存元素。作为集合的一部分，它具有所有基本的集合操作。特定于其标识的操作涉及存储在其中的元素的插入，提取和检查。这些操作中的每一个都有两种不同的形式，例如一种在操作失败时引发异常，而另一种则根据操作返回特殊值，例如null或false。注意与典型的队列不同，Java 队列的具体实现不必一定以FIFO方式对元素进行排序。对于基于优先级的队列尤其如此，其中元素的排序是根据提供的比较器或自然排序完成的。但是无论顺序如何，remove（）或poll（）方法将始终检索队列开头的元素。这两种不太可能的方法之间的特定区别似乎是相似的方法，即在失败时引发异常（NoSuchElementException），而后者则返回特殊值（null）。

而且，Queue 接口不适用于并发编程，因为它没有定义阻塞队列方法，在这种方法中，入队和出队过程等待元素出现在队列中或大小可用。有一个名为BlockingQueue 的特定接口，该接口扩展了Queue 接口并解决了这些问题。

有一个称为AbstractQueue 的抽象类，该类提供某些队列操作的部分实现。所述的PriorityQueue 类是这个抽象类的直接延伸。

优先级队列的Java实现是一种特殊的队列，其中元素的排序由其自然排序原则确定，也可以根据创建过程中提供的Comparator进行自定义。我们在构造过程中调用的构造函数决定要与优先级队列一起使用的排序原则。与Queue 不允许使用null元素不同，但是某些实现（例如LinkedList）也不禁止插入null元素。但是PriorityQueue 根本不允许空元素。如果优先级队列是根据自然顺序构造的，则任何不可比较的元素插入都会抛出ClassCastException。

它被声明为无限制的并且基于优先级堆。尽管队列的大小被称为无限制，但内部具有确定阵列大小的能力。插入元素时，此大小会自动增长。但是，未详细说明增大尺寸的原理。

七种类型的重载构造函数，通过它们我们可以设置参数来指定队列的初始容量，提供Comparator来指定元素的自定义顺序，或者使用无参数构造函数将所有内容接受为默认值。下面是这七种重载构造函数：

PriorityQueue（）

PriorityQueue（int initialCapacity）

PriorityQueue（int initialCapacity，Comparator <？Super E>比较器）

PriorityQueue（Commection <？扩展E> c）

PriorityQueue（Comparator <？Super E>比较器）

PriorityQueue（PriorityQueue <？扩展E> c）

PriorityQueue（SortedSet <？扩展E> c）

与Queue 相似，PriorityQueue 也不同步，因此在并发编程中应谨慎使用。但是，有一个同步的替代方法，称为PriorityBlockingQueue 。这与PriorityQueue 的工作方式相同，只是具有线程安全性的其他限定条件。

PriorityQueue 中定义的操作与Queue 相同，但有一些附加功能。

让我们用一个简单的程序实现PriorityQueue 的一些操作。

package org.mano.examples;

import java.util.Arrays;

import java.util.Iterator;

import java.util.PriorityQueue;

public class Example1 {

   public static void main(String[] args){

      PriorityQueue pq = new PriorityQueue<>();

      pq.add("Mercury");

      pq.add("Venus");

      pq.add("Earth");

      pq.add("Mars");

      pq.add("Jupiter");

      pq.add("Saturn");

      //  获取基于最优先元素

     //  string中自然字母排序

      System.out.println("Priority element "+pq.peek());

      //队列元素

      show(pq);

      // 删除队列元素的顶部    

  pq.poll();

      show(pq);

      // 从队列的开头检索元素

      pq.remove("Earth");

      show(pq);

      String result = pq.contains("Earth")?

         "Found Earth":"Earth Missing!";

      System.out.println(result);

      Object[] arr = pq.toArray();

      Arrays.sort(arr);

      System.out.println("");

      for (int i = 0; i

         System.out.print(arr[i].toString()+"::");

   }

   public static void show(PriorityQueue pq){

      Iterator itr = pq.iterator();

      while (itr.hasNext())

         System.out.print(itr.next()+"::");

         System.out.println("");

   }

}

输出：

Priority element Earth

Earth::Jupiter::Mercury::Venus::Mars::Saturn::

Jupiter::Mars::Mercury::Venus::Saturn::

Jupiter::Mars::Mercury::Venus::Saturn::

Earth Missing!

 

Jupiter::Mars::Mercury::Saturn::Venus::

我们举另外一个带有自定义比较器的快速示例：

package org.mano.examples;

import java.util.Comparator;

import java.util.PriorityQueue;

public class Planet implements Comparable{

   private String name;

   private double orbitPeriodInDays;

   public Planet(String name, double orbitPeriodInDays) {

      this.name = name;

      this.orbitPeriodInDays = orbitPeriodInDays;

   }

   public String getName() {

      return name;

   }

   public void setName(String name) {

      this.name = name;

   }

   public double getOrbitPeriodInDays() {

      return orbitPeriodInDays;

   }

   public void setOrbitPeriodInDays(double orbitPeriodInDays) {

      this.orbitPeriodInDays = orbitPeriodInDays;

   }

   @Override

   public int compareTo(Planet o) {

      return 0;

   }

   @Override

   public String toString() {

      return "Planet{" +

         "name='" + name + '\'' +

         ", orbitPeriodInDays=" + orbitPeriodInDays +

         '}';

   }

   public static void main(String[] args){

      Comparator nameSorter =

         Comparator.comparing(Planet::getName);

      PriorityQueue priorityQueue = new

         PriorityQueue<>(nameSorter);

      priorityQueue.add(new Planet("Mercury",88));

      priorityQueue.add(new Planet("Venus",225));

      priorityQueue.add(new Planet("Earth",365.24));

      priorityQueue.add(new Planet("Mars",693.5));

      priorityQueue.add(new Planet("Jupiter",4343.5));

      priorityQueue.add(new Planet("Saturn",10767.5));

      priorityQueue.add(new Planet("Uranus",30660));

      priorityQueue.add(new Planet("Neptune",60152));

      Object[] list = priorityQueue.toArray();

      for (Object o: list)

         System.out.println(o);

   }

}

输出：

Planet{name='Earth', orbitPeriodInDays=365.24}

Planet{name='Jupiter', orbitPeriodInDays=4343.5}

Planet{name='Mercury', orbitPeriodInDays=88.0}

Planet{name='Neptune', orbitPeriodInDays=60152.0}

Planet{name='Mars', orbitPeriodInDays=693.5}

Planet{name='Saturn', orbitPeriodInDays=10767.5}

Planet{name='Uranus', orbitPeriodInDays=30660.0}

Planet{name='Venus', orbitPeriodInDays=225.0}

除此之外，优先级队列还有不常用到的一些规范，比如从列表中删除的项目具有最高优先级。Java将优先级规则强加给其他常规队列的方式是通过附加元素的排序原则。该顺序可以根据程序员的要求进行定制，也可以设置为默认。这就是Java中优先级队列实现的本质。