链表 结构 解读 Java 并发队列 BlockingQueue(13)

private static <T> void siftUpComparable(int k, T x, Object[] array) {

Comparable<? super T> key = (Comparable<? super T>) x;

while (k > 0) {

// 二叉堆中 a[k] 节点的父节点位置

int parent = (k - 1) >>> 1;

Object e = array[parent];

if (key.compareTo((T) e) >= 0)

break;

array[k] = e;

k = parent;

}

array[k] = key;

}

我们用图来示意一下，我们接下来要将 11 插入到队列中，看看 siftUp 是怎么操作的。

我们再看看 take 方法：

public E take() throws InterruptedException {

final ReentrantLock lock = this.lock;

// 独占锁

lock.lockInterruptibly();

E result;

try {

// dequeue 出队

while ( (result = dequeue()) == null)

notEmpty.await();

} finally {

lock.unlock();

}

return result;

}

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;

}

}

dequeue 方法返回队头，并调整二叉堆的树，调用这个方法必须先获取独占锁。

废话不多说，出队是非常简单的，因为队头就是最小的元素，对应的是数组的第一个元素。难点是队头出队后，需要调整树。

private static <T> void siftDownComparable(int k, T x, Object[] array,

int n) {

if (n > 0) {

Comparable<? super T> key = (Comparable<? super T>)x;

// 这里得到的 half 肯定是非叶节点

// a[n] 是最后一个元素，其父节点是 a[(n-1)/2]。所以 n >>> 1 代表的节点肯定不是叶子节点

// 下面，我们结合图来一行行分析，这样比较直观简单

// 此时 k 为 0, x 为 17，n 为 9

int half = n >>> 1; // 得到 half = 4

while (k < half) {

// 先取左子节点

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-87792-13.html