优先级队列 PriorityQueue

PriorityQueue 是一个基于堆实现的无界队列，其不接受 null 值，且不支持 non-comparable 对象。可以通过 Comparator 或者 Comparable 对存储对象进行排序实现小顶堆或者大顶堆，队列会根据储存情况自动扩容。本文会介绍一些 PriorityQueue 的方法以及通过一个算法题展示其用法。

什么是堆？

堆是一种非线性结构，可以把堆看作一个数组，也可以被看作一个完全二叉树，我们可以利用堆的特性找到一个集中的重要元素。

Wiki 中是这么描述堆的：

若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。这种数据结构具有以下性质:

任意节点小于（或大于）它的所有后裔，最小元（或最大元）在堆的根上（堆序性）。

堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。

简单来说，堆是一种通过树结构维护的数组，且有特殊有序性的结构。

理解堆的结构

我们提到过堆是通过树结构维护的数组，PriorityQueue 可以通过一个数组来实现：

实际上数组的下标可以通过计算得到：

leftIndex = parentIndex * 2 + 1
rightIndex = parentIndex * 2 + 2
parentIndex = (nodeIndex - 1) / 2

这里的 leftIndex 和 rightIndex 分别指对应 parentIndex 这个父节点下标的左右两个子节点的数组下标，nodeIndex 理解为当前节点的数组下标，通过他可以推出他的父节点和两个子节点（如存在）的下标。

值得一提的是：
PriorityQueue 的 peek() 和 element() 方法的时间复杂度为 $O(1)$; add(), offer(), no-argument remove(), poll() 方法的时间复杂度都为 $O(\log n)$。

方法解析

add() 和 offer()

add(E e) 和 offer(E e) 的功能相同，都是向队列中插入元素。他们的区别在于：add(E e) 失败时会抛出异常，而 offer(E e) 会返回一个布尔值代表插入成功与否。

我们以 offer() 方法的源码来解释一些 PriorityQueue 的特性。

/**
 * Inserts the specified element into this priority queue.
 *
 * @return {@code true} (as specified by {@link Queue#offer})
 * @throws ClassCastException if the specified element cannot be
 *         compared with elements currently in this priority queue
 *         according to the priority queue's ordering
 * @throws NullPointerException if the specified element is null
 */
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;
    return true;
}

前面提到 PriorityQueue 不接受 null 因此在插入 null 时会视为插入失败。而在插入时会根据内外部比较器(Comparable or Comparator)进行比较交换。

/**
 * Inserts item x at position k, maintaining heap invariant by
 * promoting x up the tree until it is greater than or equal to
 * its parent, or is the root.
 *
 * To simplify and speed up coercions and comparisons, the
 * Comparable and Comparator versions are separated into different
 * methods that are otherwise identical. (Similarly for siftDown.)
 *
 * @param k the position to fill
 * @param x the item to insert
 */
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x, queue, comparator);
    else
        siftUpComparable(k, x, queue);
}

在队列空间不足时会进行自动扩容，原理 ArrayList 的 grow() 函数类似，简单来说就是创建一个新的更大的数组并复制过去。

/**
 * Increases the capacity of the array.
 *
 * @param minCapacity the desired minimum capacity
 */
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);
}

element() 和 peek()

两者语义相同，功能上都是获取但不弹出队首，区别在于队列为空时 element() 抛出异常，peek() 返回 null。

remove() 和 poll()

两者语义相同，功能上都是获取并弹出队首，区别在于队列为空时 remove() 抛出异常，poll() 返回 null。但是由于删除操作会改变队列结构，需要进行调整。以 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;
}

与增操作相同，通过内外部比较器进行比较并更新数组。

remove(Object o)

remove(Object o) 方法用于删除队列中与对象 o 相等的某一个元素（如果有多个相等，只删除一个）。与 remove() 相同，删除元素后需要对结构进行重新排序，源码如下：

public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1) //未找到目标对象
        return false;
    else {
        removeAt(i);
        return true;
    }
}

E removeAt(int i) {
        // assert i >= 0 && i < size;
        final Object[] es = queue;
        modCount++;
        int s = --size;
        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;
    }

在重排时，采用的方式还是内外部比较器比较交换的方式，这里就不过多赘述。

算法实战

LeetCode 253.会议室 II，是一道典型的使用 PriorityQueue 求解的问题，由于题目为会员题，这里就不贴出题目了，下面先上代码，再来看看解题思路：

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;

        // 创建小顶堆
        PriorityQueue<Integer> timeQueue =
                new PriorityQueue<>(
                        intervals.length,
                        new Comparator<Integer>() {
                            @Override
                            public int compare(Integer o1, Integer o2) {
                                return o1 - o2;
                            }
                        }
                );

        // 按会议开始时间排序
        Arrays.sort(
                intervals,
                new Comparator<int[]>() {
                    @Override
                    public int compare(int[] o1, int[] o2) {
                        return o1[0] - o2[0];
                    }
                }
        );

        // 添加第一个会议的结束时间
        timeQueue.add(intervals[0][1]);

        // 新会议的开始时间是否大于小顶堆的堆顶即最早结束最早结束时间
        // 如果大于则将堆顶出队，即腾出房间放入新的结束时间
        // 如果小于则无空闲房间需要开新房间
        // 最后输出堆的规模
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= timeQueue.peek()) {
                timeQueue.poll();
            }
            timeQueue.add(intervals[i][1]);
        }

        return timeQueue.size();
    }
}

我们在实例化时为 PriorityQueue 创建了一个外部比较器，使之结构为小顶堆（Java 中的优先队列默认就是小顶堆，这里创建了内部匿名类是为了展示写法）。

我们可以利用小顶堆的根节点为数组中最小元素的特性，如果新的会议开始时间比 PriorityQueue 的根节点小则说明需要新的房间开会，而如果大于则说明当前房间在开会前已经结束最新的会议，那么可以继续使用这个房间。最后输出堆的规模，也就是开了房间的数量。