当前位置 : 主页 > 编程语言 > java >

java中PriorityBlockingQueue的入队知识点总结

来源:互联网 收集:自由互联 发布时间:2021-04-03
在PriorityBlockingQueue中添加元素同样有四种方法,因为是树状的结构,所以在插入方法上也有所变化,是自下而上的操作过程。在入队的规则上有三个要点需要我们注意。鉴于PriorityBloc

在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); // never 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) 方法实现的。

网友评论