java中PriorityBlockingQueue的入队知识点总结

java中PriorityBlockingQueue的入队知识点总结

在PriorityBlockingQueue中添加元素同样有四种方法，因为是树状的结构，所以在插入方法上也有所变化，是自下而上的操作过程。在入队的规则上有三个要点需要我们注意。鉴于PriorityBlockingQueue入队方法主要通过offer(E)实现，所以我们就这种方法作主要讲解。

1.入队规则

（1）默认的插入规则中，新加入的元素可能会破坏小顶堆的性质，因此需要进行调整。

（2）调整的过程为：从尾部下标的位置开始，将加入的元素逐层与当前点的父节点的内容进行比较并交换，直到满足父节点内容都小于子节点的内容为止。

（3）默认的删除调整中，首先获取顶部下标和最尾部的元素内容，从顶部的位置开始，将尾部元素的内容逐层向下与当前点的左右子节点中较小的那个交换，直到判断元素内容小于或等于左右子节点中的任何一个为止。

2.入队方法

入队方法有：add(E), put(E), offer(E, timeout, TimeUnit), offer(E)

public void put(E e) {

offer(e); // nehttp://ver need to block

}

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);

//队列长度 +1

size = n + 1;

//唤醒休眠的出队线程

notEmpty.signal();

} finally {

//释放锁

lock.unlock();

}

return true;

}

可以看出前三个方法内部都是通过 offer(e) 方法实现的。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。