【java容器的刻意练习】【十六】PriorityQueue的底层结构

上一篇讲到ArrayDeque作为队列，性能碾压了LinkedList。所以，我们用顺序队列的时候，优先选择ArrayDeque。

那么，今天我们继续看看另外一种队列，优先级队列PriorityQueue。

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable

PriorityQueue继承了AbstractQueue抽象类，并实现了Serializable接口。而AbstractQueue抽象类实现了Queue接口，对其中方法进行了一些通用的封装，如下图。

PriorityQueue继承

Queue接口

PriorityQueue接口

先看看PriorityQueue内部是什么结构？

    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

调用了另外一个构造函数this，传入2个参数，其中一个参数是：

private static final int DEFAULT_INITIAL_CAPACITY = 11;

跳过去this构造函数看看：

    public PriorityQueue(int initialCapacity,
                         Comparator<super E> comparator) {
        // Note: This restriction of at least one is not actually needed,
        // but continues for 1.5 compatibility
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

    /**
     * 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

原来优先队列底层数据结构是个数组，而且这个queue数组是一个平衡的二叉堆。

平衡二叉堆

什么是平衡二叉堆？

• 每个节点，叶子数只能小于等于2
• 对于堆中的每个节点n和n的每个后代d, n <= d。
• 非空队列，最小值元素肯定在队列第0个位置，就是根节点。
• 队列（就是我们这里的queue数组）中某个位置n，它的的两个叶子肯定在队列2n+1和2(n+1)。
  最重点是第四点，对于任意位置，是可以通过线性公式快速算出叶子的位置的！那么，对于数组来说，这样的查找性能就是最高的！

这一堆概念初学者看到肯定是一脸懵逼的了。别方，我们来打个比方。

来看看古代打仗的矛兵阵。

• 要求第一个是最矮的矛兵。
• 之后每人身后要站有2名矛兵，而且都要比前面的矛兵高。
• 形成从低到高的三角形梯队。

当将军喊列队的时候，前面的矛兵喊自己的位置报数n。那么，后面矛兵就跟根据公式计算左2n+1和右2(n+1)快速找到自己的位置并进行报数。

例如，某个矛兵喊5。那么，他身后的2名矛兵就马上喊出自己位置，左边那位排队列11，右边那位矛兵排12。

这样，军队就能快速从列队和兵阵快速变换。

平衡二叉堆储存于数组中

平衡二叉堆是怎么排序和维护的呢？不着急，我们后面会慢慢讲到。先看回构造函数最后保存的一个参数comparator。

queue数组注释里面还提到一句：“如果comparator为null，则优先级队列会按照comparator或元素的自然顺序排序。”我们来看看comparator。

private final Comparator<super E> comparator;

而这个comparator是一个Comparator接口的实例，默认是空。

Comparator接口可以实现自定义排序，实现Comparator接口时，要重写compare方法：
int compare(Object o1, Object o2) 返回一个基本类型的整型

• o1 > o2，升序
• o1 < o2，降序

例如如下代码：

    static Comparator<Integer> cmp = new Comparator<Integer>() {
        public int compare(Integer o1, Integer o2) {
            // 升序排列
            return o1 > o2;
        }
    };

...
// 把比较器cmp传给PriorityQueue，实现升序排列
Queue priorityQueue = new PriorityQueue(cmp);

比较器也先到这里，后面我们继续详细说。

到现在，我们已经知道了：

PriorityQueue底层是个平衡二叉堆，用数组方式来储存，可以自定义比较器来实现想要的优先级排序。
PriorityDeque用的是小顶堆

大小顶堆