Java集合源码分析——PriorityQueue和PriorityBlockQueue

PriorityQueue

PriorityQueue是基于数组结构的，可自动扩容，每次扩容1

PriorityQueue物理上是基于数组结构来存储元素的，但是在每次添加或者删除元素之后要进行堆化

所以PriorityQueue是一个有序无界队列，默认为最大堆

属性

//初始数组大小默认为11
	private static final int DEFAULT_INITIAL_CAPACITY = 11;

	//真正存储元素的数组
    transient Object[] queue; 
 	
	//队列大小
    private int size = 0;
	
	//比较器
    private final Comparator<? super E> comparator;

	//操作次数
    transient int modCount = 0; 
           

构造方法

PriorityQueue默认是一个最小堆

如果要创建最大堆，则需要自己实现比较器

public PriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];//初始化数
    this.comparator = comparator;//初始化比较器
}
           

入队及扩容分析

public boolean add(E e) {
    return offer(e);
}
//添加元素
public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1); 
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

//扩容过程
private void grow(int minCapacity) {
    int oldCapacity = queue.length;
  
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}
           

当容量小于64时，库容为原来的两倍加2，否则扩容为原来的1.5倍

向上调整

private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x);
    else
        //默认堆化，向上调整
        siftUpComparable(k, x);
}
//向上调整
private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;//无符号右移
        Object e = queue[parent];
        //如果key大于父节点
        if (key.compareTo((E) e) >= 0)
            break;
        //父节点与当前节点进行交换
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}
           

向上调整过程：

1.首先将元素添加到队列尾部
2.然后进行堆化，即向上调整，不断与其父节点进行比较，将元素插入到合适位置
3.堆化时间复杂度Log2N，即添加元素的时间复杂度为Log2N
           

删除元素

//删除指定元素
public boolean remove(Object o) {
    int i = indexOf(o); //遍历元素找到下标 时间复杂度O(N)
    if (i == -1)
        return false;
    else {
        removeAt(i);//根据下标删除元素
        return true;
    }
}
private E removeAt(int i) {
    // assert i >= 0 && i < size;
    modCount++;
    int s = --size;//如果删除的是最后一个元素
    if (s == i) // removed last element
        queue[i] = null; //将最后一个元素置为null
    else {
        E moved = (E) queue[s];//获取最后一个元素
        queue[s] = null;//置为null
        siftDown(i, moved);//向下调整
        if (queue[i] == moved) {
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}

           

向下调整

//向下调整
private void siftDownComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>)x;
    int half = size >>> 1;        // loop while a non-leaf
    while (k < half) {
        int child = (k << 1) + 1; // assume left child is least
        Object c = queue[child];
        int right = child + 1;
        if (right < size &&
            ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
            c = queue[child = right];
        if (key.compareTo((E) c) <= 0)
            break;
        queue[k] = c;
        k = child;
    }
    queue[k] = key;
}

           

删除指定元素时，先将元素进行删除，然后将最后一个元素放到被删除的元素位置处，再进行下沉操作

删除元素时间复杂度O(N)，向下调整时间复杂度O(Log2N）

小结

PriorityQueue是一个以数组为结构，具有动态扩展能力的无界队列，其中数组中的元素有序，在进行添加或者删除元素之后会进行堆化，默认为最小堆

1.PriorityQueue是线程不安全的
2.常用场景：存储的数据具有优先级
           

PriorityBlockQueue

PriorityBlockQueue是一个线程安全的基于数组的优先阻塞队列，默认为最小堆

属性

//默认初始值
    private static final int DEFAULT_INITIAL_CAPACITY = 11;
 
    //安全最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    //真实存储数据的数组
    private transient Object[] queue;
	
    //比较器
    private transient Comparator<? super E> comparator;
    
    //锁
    private final ReentrantLock lock;

    private final Condition notEmpty;
           

构造方法

public PriorityBlockingQueue(int initialCapacity,
                             Comparator<? super E> comparator) {
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.lock = new ReentrantLock();//设置锁
    this.notEmpty = lock.newCondition();
    this.comparator = comparator;//比较器
    this.queue = new Object[initialCapacity];//初始化数组
}
           

入队

public boolean add(E e) {
    return offer(e);
}

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);
        size = n + 1;
        notEmpty.signal();
    } finally {
        lock.unlock();
    }
    return true;
}
           

总结

PriorityQueue与PriorityBlockQueue结构、入队、出队操作及扩容和堆化方式一致
PriorityBLockQueue是一个阻塞队列，即线程安全的