Java集合之优先队列PriorityQueue

PriorityQueue

源自java.util.PriorityQueue，继承结构：

java.lang.Object
    java.util.AbstractCollection<E>
        java.util.AbstractQueue<E>
            java.util.PriorityQueue<E>

PriorityQueue也就是优先队列，优先队列里面的元素是有序的（元素本身自然有序，或者通过Comparator能够进行比较），元素不允许为null值或者不可比较的值。队列的头是所有元素中最小的，如果有多个，则返回其中一个（任意的，即不稳定排序）。iterator()方法返回的队列的迭代器，需要注意的是迭代器返回的元素是无序。PriorityQueue不是线程安全的，如果需要线程安全的队列，可以使用PriorityBlockingQueue

代码

优先队列是使用数组来实现的，并用来表示堆的逻辑接口。类中主要的属性：

// 当前节点的左孩子为2n+1，右孩子为2n+2
transient Object[] queue
// 队列的大小，可以在构造方法中传递
private int size = 0;
// modCount用来记录队列修改的次数
transient int modCount = 0;

相关方法：

add：队列中添加元素

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

可以看到直接调用的是offer方法,offer也是给队列中添加元素：

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        //队列扩容，度列长度小于64直接double，大于64，增长50%
        // 队列的最大容量为Integer.MAX_VALUE - 8
        // 多余的8个用来针对有些虚拟机需要保留额外的信息
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        // 上浮操作
        siftUp(i, e);
    return true;
}

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];
        // 如果当前节点比父亲节点大，停止查找，表示位置是合适的
        // 如果小，则继续向上查找，并且逻辑上交换一下元素
        if (key.compareTo((E) e) >= 0)
            break;
        // k位置放父亲节点
        queue[k] = e;
        // 从父亲节点的位置继续向上找
        k = parent;
    }
    queue[k] = key;
}

另一个比较关键的方法是poll，用来从堆中弹出元素：

public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    // 每次都是返回第一个元素
    E result = (E) queue[0];
    // 获取最后一个元素
    E x = (E) queue[s];
    // 将最后一个元素置为空
    queue[s] = null;
    if (s != 0)
        // 下沉操作，将x放在堆的头部，然后下沉和合适的位置
        siftDown(0, x);
    return result;
}

private void siftDown(int k, E x) {
    if (comparator != null)
        siftDownUsingComparator(k, x);
    else
        siftDownComparable(k, x);
}
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;
}