PriorityQueue源码解析（基于JDK1.8）

目录

一、继承关系与层次结构

二、基本属性

三、构造函数

四、主要方法

add 添加对象

poll删除对象

 peek取值,获取堆顶元素

indexOf获取后一位置的元素

五、API

1.构造函数

2.常用功能函数

3.用法示例

4.安全性

一、继承关系与层次结构

public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable {......
}
public abstract class AbstractQueue<E> extends AbstractCollection<E> implements Queue<E> {......
}

优先队列的作用是能保证每次取出的元素都是队列中权值最小的，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator）。
Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。

二、基本属性

private static final int DEFAULT_INITIAL_CAPACITY = 11;transient Object[] queue;private int size = 0;private final Comparator<? super E> comparator;transient int modCount = 0;  

由上可知 ： PriorityQueue 里面维护了一个Object数组对象 ，且默大小为11

三、构造函数

    public PriorityQueue() {this(DEFAULT_INITIAL_CAPACITY, null);}// 可以使用外排序 Comparator 来构建你自己的堆，默认为空
// initialCapacity 为初始堆大小，一般来说，为了避免扩容，或者空间浪费，我们要选择合适的值，默认值为 DEFAULT_INITIAL_CAPACITY = 11public PriorityQueue(int initialCapacity,Comparator<? super E> comparator) {// Note: This restriction of at least one is not actually needed,// but continues for 1.5 compatibilityif (initialCapacity < 1)throw new IllegalArgumentException();this.queue = new Object[initialCapacity];this.comparator = comparator;}

四、主要方法

add 添加对象

    public boolean add(E e) {return offer(e);  }public boolean offer(E e) {if (e == null)throw new NullPointerException(); // 这是该对象不能加入null值最好例证modCount++;int i = size;if (i >= queue.length)grow(i + 1); // 扩容方法size = i + 1;if (i == 0)queue[0] = e;elsesiftUp(i, e); // 保持二叉堆结构，调整方法return true;}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));// 当小于64时，表示堆高在6层内时，每次扩容为原来的1倍+2 ，当大于6层时，每次扩容原来的50%    // 层高计算方式为 H=log(Length) ,但当length为2的次方时，H=log(Length)+1//上面64，因为是2的6次方，代入到公式中为log64+1 =7,但为为是<号，所以实则表示6层，未到7层// overflow-conscious codeif (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);queue = Arrays.copyOf(queue, newCapacity);}private void siftUp(int k, E x) {// 如果没有外排序，则使用内排序if (comparator != null)siftUpUsingComparator(k, x);elsesiftUpComparable(k, x);}

siftUp（）方法，需要判断有没有比较器，我们就以siftUpUsingComparator(k, x)为例

private void siftUpUsingComparator(int k, E x) {while (k > 0) {int parent = (k - 1) >>> 1;Object e = queue[parent];if (comparator.compare(x, (E) e) >= 0)break;queue[k] = e;k = parent;}queue[k] = x;
}

通过 (k-1)>>>1，位移运算符，获得父节点的索引，然后得到它的值 Object e ,比较父节点e和传入的对象x,如果，子节点比父节点大，那么，break跳出while循环 ; 但如果子节点值不如父节点，那么，它们的值交换位置，并且，此时，仍在while循环里面，会层层和父节点比较，如果发生父节点比子节点大的情况，会一直交换值，直到对象x，到达堆顶

poll删除对象

poll方法的原理， 从堆顶册除对象a，并且堆中最末位b对象替换堆顶值，然后下沉排序，（拿到根节点下的左右节点，并且判断左右节点的大小，b如果值>子节点，和子节点中中最小值进行替换，循环）

    public E poll() {if (size == 0)return null;int s = --size;modCount++;E result = (E) queue[0];E x = (E) queue[s];queue[s] = null;if (s != 0)siftDown(0, x);return result;}private void siftDown(int k, E x) {if (comparator != null)siftDownUsingComparator(k, x);elsesiftDownComparable(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;}

 peek取值,获取堆顶元素

public E peek() {return (size == 0) ? null : (E) queue[0];
}

indexOf获取后一位置的元素

// 因为使用的是最堆的数据结构，所以只能遍历，效率较低
private int indexOf(Object o) {if (o != null) {for (int i = 0; i < size; i++)if (o.equals(queue[i]))return i;}return -1;
}

五、API

1.构造函数

PriorityQueue()
PriorityQueue(Collection<? extends E> c)
PriorityQueue(int initialCapacity)
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)
PriorityQueue(PriorityQueue<? extends E> c)
PriorityQueue(SortedSet<? extends E> c)

2.常用功能函数

3.用法示例

上面提到具有优先级，那么这里举个例子。我在上高中的时候，每月分一次班级，老师会按照本月月考的成绩来让每位同学优先选择自己心仪的座位。这里所有的同学便是一个队列；每次喊一个人进来挑选座位，这便是出对的操作；成绩由前至后，这边是优先的策略。

代码示例如下：

public class PriorityQueueTest {public static void main(String[] args) {final PriorityQueue<Student> queue=new PriorityQueue<>();Student p1=new Student(95,"张三");Student p2=new Student(89,"李四");Student p3=new Student(89,"李四");Student p4=new Student(67,"王五");Student p5=new Student(92,"赵六");queue.add(p1);queue.add(p2);queue.add(p3);//add 和offer效果一样。queue.offer(p4);//add 方法实现，其实就是调用了offerqueue.offer(p5)for (Student Student : queue) {System.out.println(Student.toString());}System.out.println("---------------------");while(!queue.isEmpty()){System.out.println(queue.poll());}       }}
class Student implements Comparable{private int score;private String name;public Student(int age,String name){this.score=age;this.name=name;}public int getScore() {return score;}public void setScore(int score) {this.score = score;}public String getName() {return name;}public void setName(String name) {this.name = name;}public String toString(){return "姓名："+name+"-"+score+"分";}@Overridepublic int compareTo(Object o) {Student current=(Student)o;if(current.getScore()>this.score){return 1;}else if(current.getScore()==this.score){return 0;}return -1;}
}

运行结果：

姓名：张三-95分
姓名：赵六-92分
姓名：王五-67分
姓名：李四-89分
---------按顺序出队选座位------------
姓名：张三-95分
姓名：赵六-92分
姓名：李四-89分
姓名：李四-89分
姓名：王五-67分

从第一部分输出可以看出，学生入队并不是 按顺序的，而在poll出来的时候是按顺序出队的，这里确实实现了分数高这优先选座位的效果，poll方法返回的总是队列剩余学生中分数最高的。

4.安全性

查看PriorityQueue类的源码，会发现增加操作，并不是原子操作。没有使用任何锁。那么，如果是在多线程环境，肯定是不安全的。下面给出例子，开启多个线程，调用同一个方法对Queue进行添加元素。然后输出结果。

public class PriorityQueueTest {static final PriorityQueue<Integer> queue=new PriorityQueue<>();/**
     * 向队列中插入元素
     * @param number
     */public  void add(int number){if(!queue.contains(number)){System.out.println(Thread.currentThread()+"："+number);queue.add(number);}}   public static void main(String[] args) throws InterruptedException {final PriorityQueueTest qt=new PriorityQueueTest();final Random r=new Random();Thread t1=new Thread(){public void run(){System.out.println("t1开始运行...");for(int i=0;i<10;i++){qt.add(r.nextInt(10));}}};Thread t2=new Thread(){public void run(){System.out.println("t2开始运行...");for(int i=0;i<10;i++){qt.add(r.nextInt(10));}}};Thread t3=new Thread(){public void run(){System.out.println("t3开始运行...");for(int i=0;i<10;i++){qt.add(r.nextInt(10));}}};t1.start();t2.start();t3.start();t1.join();t2.join();t3.join();System.out.println("------ 运行结果 ---------");while(!queue.isEmpty()){System.out.println(queue.poll());}}
}

运行结果

t2开始运行...
t3开始运行...
t1开始运行...
------ 运行结果 ---------
0
1
1
2
3
4
5
6
7
8
9
9

结果中我们可以看到，具有两个1，两个9.这是不符合我们预期的，我们预期的是not contains 才插入，现在的出现的了重复的。上面的例子只需要在add方法上加锁，才可以达到我们预期的效果。所以说，PriorityQueue是非线程安全的。