java中PriorityBlockingQueue的入队

Z时代
2024-01-10
分类：综合

美女程序员鼓励师

本教程操作环境：windows7系统、java10版，DELL G3电脑。

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