优先队列PriorityQueue，有空了解一下吗？

前言

PriorityQueue这个队列不知道大家使用过吗，反正我用的很少，主要对它不是很了解，今天我带领大家剖析下PriorityQueue这个优先级队列。

PriorityQueue介绍

顾名思义，PriorityQueue是优先队列的意思。优先队列的作用是能保证每次取出的元素都是队列中权值最小的。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器。

• PriorityQueue实现了Queue接口，最大的特点是存取具有优先级，就是根据元素的顺序来决定
• PriorityQueue是一个无界的容器
• PriorityQueue底层是基于堆实现的
• 不允许放入null元素
• PriorityQueue不是线程安全的

图片

以上是PriorityQueue的类图,

• 继承了AbstractQueue抽象类，实现了Queue接口，具备队列的操作方法
• 实现了Seriablizable接口，支持序列化

构造方法

关键方法

使用案例

1. 优先队列功能测试

@Test
    public void test1() {
        Queue<Integer> queue = new PriorityQueue<>();
        queue.offer(5);
        queue.offer(4);
        queue.offer(1);
        queue.offer(9);
        queue.offer(3);
        queue.offer(2);

        // 打印，排序
        Integer poll = null;
        while ((poll = queue.poll()) != null) {
            System.out.println(poll);
        }
    }

运行结果：

图片

1. 自定义排序器

@Test
    public void test2() {
        // 自定义排序，倒序
        Queue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        queue.offer(5);
        queue.offer(4);
        queue.offer(1);
        queue.offer(9);
        queue.offer(3);
        queue.offer(2);

        // 打印，排序
        Integer poll = null;
        while ((poll = queue.poll()) != null) {
            System.out.println(poll);
        }
    }

运行结果：

图片

实现机制

PriorityQueue通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。

图片

上图中我们给每个元素按照层序遍历的方式进行了编号，如果你足够细心，会发现父节点和子节点的编号是有联系的，更确切的说父子节点的编号之间有如下关系：

leftNo = parentNo*2+1

rightNo = parentNo*2+2

parentNo = (nodeNo-1)/2

通过上述三个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。

源码解析

成员变量

transient Object[] queue;
    /**
     * The number of elements in the priority queue.
     */
private int size = 0;

    /**
     * The comparator, or null if priority queue uses elements'
     * natural ordering.
     */
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;

• queue就是实际存储元素的数组。
• size表示当前元素个数。
• comparator为比较器，可以为null。
• modCount记录修改次数。

构造方法

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

• 初始化了queue和comparator

添加元素offer

public boolean offer(E e) {
        // 如果元素为空，抛出空指针
        if (e == null)
            throw new NullPointerException();
        // 修改次数+1
        modCount++;
        int i = size;
        // 首先确保数组长度是够的，如果不够，调用grow方法动态扩展。
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        // 如果是第一次添加，直接添加到第一个位置即可 (queue[0]=e)
        if (i == 0)
            queue[0] = e;
        else
            // 否则将其放入最后一个位置，但同时向上调整，直至满足堆的性质 (siftUp) 
            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);
    }

如果原长度比较小，大概就是扩展为两倍，否则就是增加50%，使用Arrays.copyOf方法拷贝数组。

private void siftUp(int k, E x) {
        // 如果比较器为空
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

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

参数k表示插入位置，x表示新元素。k初始等于数组大小，即在最后一个位置插入。代码的主要部分是：往上寻找x真正应该插入的位置，这个位置用k表示。

怎么找呢？新元素(x)不断与父节点(e)比较，如果新元素(x)大于等于父节点(e)，则已满足堆的性质，退出循环，k就是新元素最终的位置，否则，将父节点往下移(queue[k]=e)，继续向上寻找。

总结

优先级可以有相同的，内部元素不是完全有序的，如果遍历输出，除了第一个，其他没有特定顺序。查看头部元素的效率很高，为O(1)，入队、出队效率比较高，为O(log2(N))，构建堆的效率为O(N)。根据值查找和删除元素的效率比较低，为O(N)。