Java数据结构之PriorityQueue

Queue（队列）是拥有 先进先出 （FIFO）特性的数据结构，PriorityQueue（优先级队列）是它的子类之一，不同于先进先出，它可以通过比较器控制元素的输出顺序（优先级）。本文就来分析一下PriorityQueuede的源码，看看它是如何实现的。

类继承关系

先来看 Queue 接口：

public interface Queue<E> extends Collection<E>
复制代码

Queue接口继承了Collection接口，表示集合。它提供了三种方法，即：增加、删除、获取，每种都有两个实现。

// 增加元素
boolean add(E e);
boolean offer(E e);
// 删除元素
E remove();
E poll();
// 获取元素
E element();
E peek();
复制代码

两种实现的区别是， add 、 remove 和 element 都比对应的 offer 、 poll 和 peek 多抛出一个异常。对于 add 方法，如果因为容量不足以增加新元素，会抛出 IllegalStateException 异常，而 offer 则会返回false。对于 remove 方法，如果队列是空的，则会抛出 NoSuchElementException 异常，而 poll 方法会返回null。对于 element 方法，如果队列是空的，则会抛出 NoSuchElementException 异常，而 peek 方法会返回null。

再看 PriorityQueue 类：

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable
复制代码

嗯，不是直接实现 Queue ，而是继承了 AbstractQueue 类。又是熟悉的感觉， AbstractQueue 应该也是模板抽象类（和AbstractMap和AbstractList类似）。

来看 AbstractQueue ：

public abstract class AbstractQueue<E>
    extends AbstractCollection<E>
    implements Queue<E>
复制代码

果然，继承了 AbstractCollection 类和实现了 Queue 接口。既然是模板类那肯定有模板方法。 AbstractQueue 源码中只实现了 add 、 remove 和 elemet 方法。

public boolean add(E e) {
        if (offer(e)) // 调用offer
        ...
    }
    
public E remove() {
        E x = poll(); // 调用poll
        ...
    }
    
public E element() {
        E x = peek(); // 调用peek
        ...
    }
复制代码

可以看到，它们分别调用了 offer 、 poll 和 peek 。也就是说，如果要通过 AbstractQueue 实现队列，则必须实现 offer 、 poll 和 peek 方法。

下面就正紧的分析 PriorityQueue 的源码了。

PriorityQueue源码分析

纵观源码，发现PriorityQueue是通过“极大优先级堆”实现的，即堆顶元素是优先级最大的元素。算是集成了大根堆和小根堆的功能。

重要属性

根据堆的特性，存储结构肯定是数组了；既然支持不同优先级，肯定有比较器，也就是说支持自定义排序和顺序排序。

// 默认容量11
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 堆的存储结构，存储元素
transient Object[] queue; // 不可序列化
// 当前存储的元素数量
int size;
// 比较器，确定优先级高低
private final Comparator<? super E> comparator;
// 避免OOM，数组可以分配的最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
复制代码

构造函数

PriorityQueue的构造函数有很多，主要参数是容量和比较器：

public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null); // 默认自然序
    }

public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null); // 自定义初始容量
    }
    
public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator); // 自定义比较器
    }
    
public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        ... // 对应赋值
    }

public PriorityQueue(Collection<? extends E> c) {
        // 将c转成堆
        if (c instanceof SortedSet<?>) {
            ... // SortedSet自带比较器
        }
        else if (c instanceof PriorityQueue<?>) {
            ... // PriorityQueue自带比较器
        }
        else {
            ...
        }
    }
    
public PriorityQueue(PriorityQueue<? extends E> c) {
        ... // 从PriorityQueue获取比较器，将c转成堆
    }
    
public PriorityQueue(SortedSet<? extends E> c) {
        ...// 从SortedSet获取比较器，将c转成堆
    }
复制代码

重用方法

PriorityQueue是支持扩容的，先来看扩容方法：

// minCapacity表示需要的最小容量
private void grow(int minCapacity) {
        int oldCapacity = queue.length; // 获取当前容量
        // Double size if small; else grow by 50%
        // 如果旧容量小于64，则增加旧容量+2的大小
        // 如果旧容量大于等于64，则增加旧容量的一半大小
        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); // 复制已存储的数据
    }
复制代码

每次扩展的容量大小还是挺大的，要么变为原来的双倍，要么增长一半大小。

在看增加元素、删除元素和获取元素的方法之前，先了解以下几点：

1. 完全二叉树的最后一个非叶子结点的下标是 (n-2) / 2；
2. 完全二叉树中如果一个非叶子结点的下标是i，则它的父结点下标是（i-1）/2，它的左孩子下标是 2 * i + 1，右孩子下标是 2 * i + 2；

offer方法

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1); // 如果超出当前容量，则进行扩容
        siftUp(i, e); // 新元素都是增加在数组尾部，然后进行上移操作，即构建堆
        size = i + 1; // 当前大小加1
        return true;
    }
复制代码

siftUp 方法最终会调用 siftUpUsingComparator 或者 siftUpComparable 方法，两个实现类似，这里直接看 siftUpUsingComparator 方法。

// 上移就是不断和父结点比较
private static <T> void siftUpUsingComparator(
        int k, T x, Object[] es, Comparator<? super T> cmp) {
        while (k > 0) {
            int parent = (k - 1) >>> 1; // 父结点下标
            Object e = es[parent];
            if (cmp.compare(x, (T) e) >= 0) // 优先级高则继续上移比较
                break;
            es[k] = e;
            k = parent;
        }
        es[k] = x;
    }
复制代码

每次增加元素，都要保证堆序。

poll方法

public E poll() {
        final Object[] es;
        final E result;
        // 返回堆顶元素
        if ((result = (E) ((es = queue)[0])) != null) {
            modCount++;
            final int n;
            final E x = (E) es[(n = --size)]; // 把尾部元素换到第一个
            es[n] = null;
            if (n > 0) {
                final Comparator<? super E> cmp;
                if ((cmp = comparator) == null) // 自然序时，下移调整
                    siftDownComparable(0, x, es, n);
                else // 自定义序下移调整
                    siftDownUsingComparator(0, x, es, n, cmp);
            }
        }
        return result;
    }
复制代码

poll方法会返回队首元素（堆顶），并将元素从堆中删除。删除过程，是将第一个元素与最后一个元素进行替换，然后再进行下移调整操作。这里直接看 siftDownUsingComparator 方法：

private static <T> void siftDownUsingComparator(
        int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
        // assert n > 0;
        int half = n >>> 1; // 最后一个非叶子结点下标（因为size已经减1了）
        while (k < half) {
            int child = (k << 1) + 1; // 左孩子
            Object c = es[child];
            int right = child + 1; // 右孩子
            if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
                c = es[child = right]; // 从左右孩子中挑选优先级高的
            if (cmp.compare(x, (T) c) <= 0)
                break;
            es[k] = c; // 将目标元素下移
            k = child;
        }
        es[k] = x;
    }
复制代码

每次弹出队首元素，都要进行堆调整。

remove方法

poll方法可以看出是remove方法的特例，即固定删除第一个元素。

public boolean remove(Object o) {
        int i = indexOf(o); // 找到待删除元素位置
        if (i == -1)
            return false;
        else {
            removeAt(i); // 删除指定位置元素
            return true;
        }
    }
复制代码

调用了 removeAt 方法：

E removeAt(int i) {
        // assert i >= 0 && i < size;
        final Object[] es = queue;
        modCount++;
        int s = --size; // size已经减1
        if (s == i) // removed last element
            es[i] = null; // 已经删除到最后一个元素
        else {
            E moved = (E) es[s]; // 尾元素
            es[s] = null;
            siftDown(i, moved); // 指定元素换尾元素，然后调整
            if (es[i] == moved) {
                siftUp(i, moved); // 如果指定位置换成了尾元素（没有发生下移）则进行上移操作
                if (es[i] != moved)
                    return moved;
            }
        }
        return null; // 正常删除时返回null
    }
复制代码