解析Java中PriorityQueue优先级队列结构的源码及用法

一、priorityqueue的数据结构

jdk7中priorityqueue（优先级队列）的数据结构是二叉堆。准确的说是一个最小堆。

二叉堆是一个特殊的堆， 它近似完全二叉树。二叉堆满足特性：父节点的键值总是保持固定的序关系于任何一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆。
当父节点的键值总是大于或等于任何一个子节点的键值时为最大堆。 当父节点的键值总是小于或等于任何一个子节点的键值时为最小堆。
下图是一个最大堆

priorityqueue队头就是给定顺序的最小元素。

priorityqueue不允许空值且不支持non-comparable的对象。priorityqueue要求使用comparable和comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。

priorityqueue的大小是无限制的（unbounded）, 但在创建时可以指定初始大小。当增加队列元素时，队列会自动扩容。

priorityqueue不是线程安全的， 类似的priorityblockingqueue是线程安全的。

我们知道队列是遵循先进先出（first-in-first-out）模式的，但有些时候需要在队列中基于优先级处理对象。举个例子，比方说我们有一个每日交易时段生成股票报告的应用程序，需要处理大量数据并且花费很多处理时间。客户向这个应用程序发送请求时，实际上就进入了队列。我们需要首先处理优先客户再处理普通用户。在这种情况下，java的priorityqueue(优先队列)会很有帮助。

priorityqueue是基于优先堆的一个*队列，这个优先队列中的元素可以默认自然排序或者通过提供的comparator（比较器）在队列实例化的时排序。
优先队列不允许空值，而且不支持non-comparable（不可比较）的对象，比如用户自定义的类。优先队列要求使用java comparable和comparator接口给对象排序，并且在排序时会按照优先级处理其中的元素。

优先队列的头是基于自然排序或者comparator排序的最小元素。如果有多个对象拥有同样的排序，那么就可能随机地取其中任意一个。当我们获取队列时，返回队列的头对象。

优先队列的大小是不受限制的，但在创建时可以指定初始大小。当我们向优先队列增加元素的时候，队列大小会自动增加。

priorityqueue是非线程安全的，所以java提供了priorityblockingqueue（实现blockingqueue接口）用于java多线程环境。

二、priorityqueue源码分析

成员：

priavte transient object[] queue;
private int size = 0;

1.priorityqueue构造小顶堆的过程

这里我们以priorityqueue构造器传入一个容器为参数priorityqueue(collecntion<? extends e>的例子：

构造小顶堆的过程大体分两步：

复制容器数据，检查容器数据是否为null

private void initelementsfromcollection(collection<? extends e> c) {
  object[] a = c.toarray();
  // if c.toarray incorrectly doesn't return object[], copy it.
  if (a.getclass() != object[].class)
    a = arrays.copyof(a, a.length, object[].class);
  int len = a.length;
  if (len == 1 || this.comparator != null)
    for (int i = 0; i < len; i++)
      if (a[i] == null)
        throw new nullpointerexception();
  this.queue = a;
  this.size = a.length;
}

调整，使数据满足小顶堆的结构。
首先介绍两个调整方式siftup和siftdown

siftdown: 在给定初始化元素的时候，要调整元素，使其满足最小堆的结构性质。因此不停地从上到下将元素x的键值与孩子比较并做交换，直到找到元素x的键值小于等于孩子的键值（即保证它比其左右结点值小），或者是下降到叶子节点为止。
例如如下的示意图，调整9这个节点：

private void siftdowncomparable(int k, e x) {
  comparable<? super e> key = (comparable<? super e>)x;
  int half = size >>> 1;    // size/2是第一个叶子结点的下标
  //只要没到叶子节点
  while (k < half) {
    int child = (k << 1) + 1; // 左孩子
    object c = queue[child];
    int right = child + 1;
    //找出左右孩子中小的那个
    if (right < size &&
      ((comparable<? super e>) c).compareto((e) queue[right]) > 0)
      c = queue[child = right];
    if (key.compareto((e) c) <= 0)
      break;
    queue[k] = c;
    k = child;
  }
  queue[k] = key;
}

siftup: priorityqueue每次新增加一个元素的时候是将新元素插入对尾的。因此，应该与siftdown有同样的调整过程，只不过是从下（叶子）往上调整。
例如如下的示意图，填加key为3的节点：

private void siftupcomparable(int k, e x) {
  comparable<? super e> key = (comparable<? super e>) x;
  while (k > 0) {
    int parent = (k - 1) >>> 1;   //获取parent下标
    object e = queue[parent];
    if (key.compareto((e) e) >= 0)
      break;
    queue[k] = e;
    k = parent;
  }
  queue[k] = key;
}

总体的建立小顶堆的过程就是：

private void initfromcollection(collection<? extends e> c) {
    initelementsfromcollection(c);
    heapify();
  }

其中heapify就是siftdown的过程。

2.priorityqueue容量扩容过程

从实例成员可以看出，priorityqueue维护了一个object[], 因此它的扩容方式跟顺序表arraylist相差不多。
这里只给出grow方法的源码

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);
  }

可以看出，当数组的capacity不大的时候，每次扩容也不大。当数组容量大于64的时候，每次扩容double。

三、priorityqueue的应用

eg1：
这里给出一个最简单的应用：从动态数据中求第k个大的数。
思路就是维持一个size = k 的小顶堆。

  //data是动态数据
  //heap维持动态数据的堆
  //res用来保存第k大的值
  public boolean kthlargest(int data, int k, priorityqueue<integer> heap, int[] res) {
    if(heap.size() < k) {
      heap.offer(data);
      if(heap.size() == k) {
        res[0] = heap.peek();
        return true;
      }
      return false;
    }
    if(heap.peek() < data) {
      heap.poll();
      heap.offer(data);
    }
    res[0] = heap.peek();
    return true;
  }

   
eg2：
我们有一个用户类customer，它没有提供任何类型的排序。当我们用它建立优先队列时，应该为其提供一个比较器对象。

customer.java

package com.journaldev.collections;
 
public class customer {
 
  private int id;
  private string name;
 
  public customer(int i, string n){
    this.id=i;
    this.name=n;
  }
 
  public int getid() {
    return id;
  }
 
  public string getname() {
    return name;
  }
 
}

我们使用java随机数生成随机用户对象。对于自然排序，我们使用integer对象，这也是一个封装过的java对象。
下面是最终的测试代码，展示如何使用priorityqueue：

priorityqueueexample.java

package com.journaldev.collections;
 
import java.util.comparator;
import java.util.priorityqueue;
import java.util.queue;
import java.util.random;
 
public class priorityqueueexample {
 
  public static void main(string[] args) {
 
    //优先队列自然排序示例
    queue<integer> integerpriorityqueue = new priorityqueue<>(7);
    random rand = new random();
    for(int i=0;i<7;i++){
      integerpriorityqueue.add(new integer(rand.nextint(100)));
    }
    for(int i=0;i<7;i++){
      integer in = integerpriorityqueue.poll();
      system.out.println("processing integer:"+in);
    }
 
    //优先队列使用示例
    queue<customer> customerpriorityqueue = new priorityqueue<>(7, idcomparator);
    adddatatoqueue(customerpriorityqueue);
 
    polldatafromqueue(customerpriorityqueue);
 
  }
 
  //匿名comparator实现
  public static comparator<customer> idcomparator = new comparator<customer>(){
 
    @override
    public int compare(customer c1, customer c2) {
      return (int) (c1.getid() - c2.getid());
    }
  };
 
  //用于往队列增加数据的通用方法
  private static void adddatatoqueue(queue<customer> customerpriorityqueue) {
    random rand = new random();
    for(int i=0; i<7; i++){
      int id = rand.nextint(100);
      customerpriorityqueue.add(new customer(id, "pankaj "+id));
    }
  }
 
  //用于从队列取数据的通用方法
  private static void polldatafromqueue(queue<customer> customerpriorityqueue) {
    while(true){
      customer cust = customerpriorityqueue.poll();
      if(cust == null) break;
      system.out.println("processing customer with id="+cust.getid());
    }
  }
 
}

注意我用实现了comparator接口的java匿名类，并且实现了基于id的比较器。
当我运行以上测试程序时，我得到以下输出：

processing integer:9
processing integer:16
processing integer:18
processing integer:25
processing integer:33
processing integer:75
processing integer:77
processing customer with id=6
processing customer with id=20
processing customer with id=24
processing customer with id=28
processing customer with id=29
processing customer with id=82
processing customer with id=96

从输出结果可以清楚的看到，最小的元素在队列的头部因而最先被取出。如果不实现comparator，在建立customerpriorityqueue时会抛出classcastexception。

exception in thread "main" java.lang.classcastexception: com.journaldev.collections.customer cannot be cast to java.lang.comparable
  at java.util.priorityqueue.siftupcomparable(priorityqueue.java:633)
  at java.util.priorityqueue.siftup(priorityqueue.java:629)
  at java.util.priorityqueue.offer(priorityqueue.java:329)
  at java.util.priorityqueue.add(priorityqueue.java:306)
  at com.journaldev.collections.priorityqueueexample.adddatatoqueue(priorityqueueexample.java:45)
  at com.journaldev.collections.priorityqueueexample.main(priorityqueueexample.java:25)