欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-03-11 14:55:55
一、priorityqueue的数据结构 jdk7中priorityqueue(优先级队列)的数据结构是二叉堆。准确的说是一个最小堆。 二叉堆是一个特殊的堆, 它近似完...

一、priorityqueue的数据结构

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

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

解析Java中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这个节点:

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

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的节点:

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

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)