优先级对列PriorityBlockingQueue

优先级对列PriorityBlockingQueue

转自：http://blog.sina.com.cn/s/blog_6145ed8101010q1y.html

 

PriorityBlockingQueue里面存储的对象必须是实现Comparable接口。队列通过这个接口的compare方法确定对象的priority。

规则是：当前和其他对象比较，如果compare方法返回负数，那么在队列里面的优先级就比较搞。

下面的测试可以说明这个断言：

查看打印结果，比较take出来的Entity和left的entity，比较他们的priority

package com.java.exam1;

import java.util.Random;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.PriorityBlockingQueue;
import java.util.concurrent.TimeUnit;

public class TestPriorityQueue {  
   
    static Random r=new Random(47);  
      
    public static void main(String args[]) throws InterruptedException{  
        final PriorityBlockingQueue q=new PriorityBlockingQueue();  
        ExecutorService se=Executors.newCachedThreadPool();  
        //execute producer  
        se.execute(new Runnable(){  
            public void run() {  
                int i=0;  
                while(true){  
                    q.put(new PriorityEntity(r.nextInt(10),i++));  
                    try {  
                        TimeUnit.MILLISECONDS.sleep(r.nextInt(1000));  
                    } catch (InterruptedException e) {  
                        // TODO Auto-generated catch block  
                        e.printStackTrace();  
                    }  
                }  
            }  
        }); 
          
        //execute consumer  
        se.execute(new Runnable(){  
            public void run() {  
                while(true){  
                    try {  
                        System.out.println("take-- "+q.take()+" left:-- ["+q.toString()+"]");  
                        try {  
                            TimeUnit.MILLISECONDS.sleep(r.nextInt(1000));  
                        } catch (InterruptedException e) {  
                            // TODO Auto-generated catch block  
                            e.printStackTrace();  
                        }  
                    } catch (InterruptedException e) {  
                        e.printStackTrace();  
                    }  
                }  
            }  
        });  
        try {  
            TimeUnit.SECONDS.sleep(5);  
        } catch (InterruptedException e) {  
            // TODO Auto-generated catch block  
            e.printStackTrace();  
        }  
        System.out.println("shutdown");  
    }  
 
}  
 
class PriorityEntity implements Comparable<PriorityEntity> {  
    private static int count=0;  
    private int id=count++;  
    private int priority;  
    private int index=0;  
 
    public PriorityEntity(int _priority,int _index) {  
        this.priority = _priority;  
        this.index=_index;  
    }  
      
    public String toString(){  
        return id+"# [index="+index+" priority="+priority+"]";  
    }  
 
    //数字小，优先级高  
    public int compareTo(PriorityEntity o) {  
        return this.priority > o.priority ? 1 
                : this.priority < o.priority ? -1 : 0;  
    }  
 
    //数字大，优先级高  
//  public int compareTo(PriorityTask o) {  
//      return this.priority < o.priority ? 1  
//              : this.priority > o.priority ? -1 : 0;  
//  }  
} 

 

问题：有没有人在使用时，发现将添加在PriorityBlockingQueue的一系列元素打印出来，队列的元素其实并不是全部按优先级排序的，但是队列头的优先级肯定是最高的？

回复：PriorityBlockingQueue队列添加新元素时候不是将全部元素进行顺序排列， 而是从某个指定位置开始将新元素与之比较，一直比到队列头，这样既能保证队列头一定是优先级最高的元素，又能减少排序带来的性能消耗（个人判断，仅供参 考），可以查看PriorityBlockingQueue源码，添加元素有调用一个方法是 PriorityQueue.siftUpUsingComparator（或siftUpComparable），这个方法里有个排序算法：

private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

不是全部排序。

但是这样会出现一个情况，取完队列头时候，后面的剩余的元素不是排序的，岂不是不符合要求了，继续查看源码，发现每取一个头元素时候，都会对剩余的元素做一次调整，这样就能保证每次队列头的元素都是优先级最高的元素，查看取元素时候调用的一个方法PriorityQueue.：

 private void siftDown(int k, E x) {
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            siftDownComparable(k, x);
    }

 private void siftDownUsingComparator(int k, E x) {
        int half = size >>> 1;
        while (k < half) {
            int child = (k << 1) + 1;
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                comparator.compare((E) c, (E) queue[right]) > 0)
                c = queue[child = right];
            if (comparator.compare(x, (E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = x;
    }