转载请注明原创地址http://www.cnblogs.com/dongxiao-yang/p/6293807.html
java.util.concurrent.PriorityBlockingQueue内部用二叉堆实现了一个优先队列，所有插入的元素必须实现java.lang.Comparable接口。由于完全二叉树可以用数组来表示，所以队列内部元素存放在可变长度数组queue里。
private transient Object[] queue; //用于存放元素的数组
一 插入元素入队
public boolean offer(E e) { if (e == null) throw new NullPointerException(); final ReentrantLock lock = this.lock; lock.lock(); int n, cap; Object[] array; while ((n = size) >= (cap = (array = queue).length)) tryGrow(array, cap); try { Comparator<? super E> cmp = comparator; if (cmp == null) siftUpComparable(n, e, array); else siftUpUsingComparator(n, e, array, cmp); size = n + 1; notEmpty.signal(); } finally { lock.unlock(); } return true; }
//新元素堆内上浮实现
private static <T> void siftUpComparable(int k, T x, Object[] array) { Comparable<? super T> key = (Comparable<? super T>) x; //尝试转化插入对象为Comparable实例 while (k > 0) { int parent = (k - 1) >>> 1; // 新元素x的数组下标为k，对应的父节点的下标为(k-1)/2 Object e = array[parent]; if (key.compareTo((T) e) >= 0) //如果子节点已经比父节点还要大，不需要再跟上层节点比较，新元素上浮结束 break; array[k] = e; //如果子节点已经比父节点小，父节点下沉，新元素上浮一次 k = parent; //新元素上浮后继续与新的父节点比较大小，直到k=0或者新的父节点小于新元素 } array[k] = key;//新元素在堆中插入正确的位置。 }
一 弹出元素出队
public E poll() { final ReentrantLock lock = this.lock; lock.lock(); try { return dequeue(); } finally { lock.unlock(); } } private E dequeue() { int n = size - 1; if (n < 0) return null; else { Object[] array = queue; E result = (E) array[0]; E x = (E) array[n]; array[n] = null; Comparator<? super E> cmp = comparator; if (cmp == null) siftDownComparable(0, x, array, n);//堆顶的最小值被弹出了，堆顶变成了空节点，空节点开始下浮到合适位置后用数组最后子节点填充。 else siftDownUsingComparator(0, x, array, n, cmp); size = n; return result; } }
//空元素堆内下沉实现
private static <T> void siftDownComparable(int k, T x, Object[] array, int n) { if (n > 0) { Comparable<? super T> key = (Comparable<? super T>) x; int half = n >>> 1; // loop while a non-leaf half最后一个有子节点的父节点下标 while (k < half) { int child = (k << 1) + 1; // assume left child is least Object c = array[child]; int right = child + 1; if (right < n && ((Comparable<? super T>) c) .compareTo((T) array[right]) > 0) c = array[child = right]; //比较出左右子节点更小的那个子节点 if (key.compareTo((T) c) <= 0) //如果左右子节点的最小值大于数组末尾的值，那么数组末尾的值直接放到父节点，空节点下沉结束 break; array[k] = c; // 如果子节点最小值小于数据末尾的值，子节点上浮到父空节点 k = child; //空节点下滑到最小子节点的位置 } array[k] = key; // 最后空节点填充数组最后的值 } }