Queue常用类解析之PriorityQueue

PriorityQueue称作优先队列，与普通队列先进先出不同，优先级队列中优先级最高的元素最先出列。

一、属性

//默认容量，初始化队列没有穿容量参数时使用
private static final int DEFAULT_INITIAL_CAPACITY = 11;

 /**
  * Priority queue represented as a balanced binary heap: the two
  * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
  * priority queue is ordered by comparator, or by the elements'
  * natural ordering, if comparator is null: For each node n in the
  * heap and each descendant d of n, n <= d.  The element with the
  * lowest value is in queue[0], assuming the queue is nonempty.
  */
  //元素数组
 transient Object[] queue; // non-private to simplify nested class access

 /**
  * The number of elements in the priority queue.
  */
  //元素数量
 private int size = 0;

 /**
  * The comparator, or null if priority queue uses elements'
  * natural ordering.
  */
  //优先级的比较器，仅当元素为Comparable时可以为null
 private final Comparator<? super E> comparator;

 /**
  * The number of times this priority queue has been
  * <i>structurally modified</i>.  See AbstractList for gory details.
  */
  //修改次数
 transient int modCount = 0; // non-private to simplify nested class access
           

队列的元素保存在数组queue中，其数据结构为最小堆，也就是用数组表示的完全二叉树。

对于下标为i的元素，其子节点的元素的下标为 2i +1 和 2i + 2，其父节点的元素的下标为 (i - 1)/2。

根据堆的特性，队列的头元素就是queue[0]，也就是队列中的最小值，可以理解为优先级最高。

因此，PriorityQueue的关键就是对节点操作（插入和删除）后如何保持堆的特性。

二、 插入元素

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;
    // Double size if small; else grow by 50%
    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);
}
           

// Double size if small; else grow by 50%

四、 删除元素

public boolean remove(Object o) {
	//找到元素下标
    int i = indexOf(o);
    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;
    else {
    	//末尾元素放到对应位置
        E moved = (E) queue[s];
        queue[s] = null;
        //下沉
        siftDown(i, moved);
        //没有发生交换
        if (queue[i] == moved) {
        	//上浮
            siftUp(i, moved);
            if (queue[i] != moved)
                return moved;
        }
    }
    return null;
}
           

五、上浮

siftUpUsingComparator基于comparator属性进行大小比较。

siftUpComparable在comparator为null时根据元素自身进行排序，要求元素必须是Comparable类型。

其余方面，两者没有差别。优先使用siftUpUsingComparator进行比较。

private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (comparator.compare(x, (E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = x;
}
           

元素x大于或等于父节点，符合堆特性，完成。

元素x小于父节点，节点交换，继续向上比较。

六、下沉

siftDownUsingComparator基于comparator属性进行大小比较。

siftDownComparable在comparator为null时根据元素自身进行排序，要求元素必须是Comparable类型。

其余方面，两者没有差别。优先使用siftDownUsingComparator进行比较。

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

元素x小于或等于子节点，符合堆特性，完成。

元素x大于父节点，与子节点中最小的节点交换，继续向下比较。