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

int child = (k << 1) + 1; // 得到 child = 1

Object c = array[child]; // c = 12

int right = child + 1; // right = 2

// 如果右子节点存在，而且比左子节点小

// 此时 array[right] = 20，所以条件不满足

if (right < n &&

((Comparable<? super T>) c).compareTo((T) array[right]) > 0)

c = array[child = right];

// key = 17, c = 12，所以条件不满足

if (key.compareTo((T) c) <= 0)

break;

// 把 12 填充到根节点

array[k] = c;

// k 赋值后为 1

k = child;

// 一轮过后，我们发现，12 左边的子树和刚刚的差不多，都是缺少根节点，接下来处理就简单了

}

array[k] = key;

}

}

记住二叉堆是一棵完全二叉树，那么根节点 10 拿掉后，最后面的元素 17 必须找到合适的地方放置。首先，17 和 10 不能直接交换，那么先将根节点 10 的左右子节点中较小的节点往上滑，即 12 往上滑，然后原来 12 留下了一个空节点，然后再把这个空节点的较小的子节点往上滑，即 13 往上滑，最后，留出了位子，17 补上即可。

我稍微调整下这个树，以便读者能更明白：

好了， PriorityBlockingQueue 我们也说完了。

总结

我知道本文过长，相信一字不漏看完的读者肯定是少数。

ArrayBlockingQueue 底层是数组，有界队列，如果我们要使用生产者-消费者模式，这是非常好的选择。

LinkedBlockingQueue 底层是链表，可以当做无界和有界队列来使用，所以大家不要以为它就是无界队列。

SynchronousQueue 本身不带有空间来存储任何元素，使用上可以选择公平模式和非公平模式。

PriorityBlockingQueue 是无界队列，基于数组，数据结构为二叉堆，数组第一个也是树的根节点总是最小值。返回搜狐，查看更多

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