PriorityQueue

一个基于优先级堆的无界优先级队列。

二叉堆

可视化操作：二叉堆

二叉堆(The binary heap)数据结构能够有效的支持基本的优先队列操作。key存储在一个数组中，其中每个key大于(或等于)指定的两个位置及以上的key

如果key节点比两个key子节点（如果有）大或等于表示这个二叉树是堆有序的。（子节点间无序）

位置

二叉堆使用完全二叉树在数组中实现，堆中节点的位置可以用数组下标很方便的表示。其中k表示数组下标

• 数组下标1开始

一个节点的父节点：k/2 向下取整

一个节点的两个子节点：左子节点2*k 右子节点2*k+1。

• 数组下标0开始

父节点：(k-1)/2 向下取整

左子节点：2*k+1

右子节点：2*(k+1) 即 (2*k+1)+1

最后一个父节点（只有存在子节点）：(size/2)-1

PriorityQueue为下标0开始

上浮（siftUp）

当一个key被添加到有序的二叉堆时，即插入到数组最后，此时会破坏堆的有序性，需要交换key使堆有序。假设使用最大优先队列即父节点大于或等于子节点

过程很简单，即比较key与父节点p位置为(k-1)/2的大小：（针对最大优先队列，如果是最小优先，颠倒符号即可）

• 如果key>p就交换两者的位置并与新的父节点继续比较
• 如果key<=p排序完成

下面是PriorityQueue的源码，注意是使用 最小堆，即自然顺序natural ordering

// 使用指定位置k的节点x向上使堆有序
private static <T> void siftUpComparable(int k, T x, Object[] es) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    // 找到key在堆中的位置  当key的位置k是根节点位置0时终止
    while (k > 0) {
        // k位置的父节点位置
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        // 如果key比父节点大或相等时 此时堆有序 最小堆
        if (key.compareTo((T) e) >= 0)
            break;
        // 将父节点e移动到子节点位置k上。此时会导致父子节点都为同一个值原来的父节点，子节点被覆盖
        es[k] = e;
        k = parent;
    }
    // 将key放到父节点位置k。
    es[k] = key;
}

下沉（siftDown）

在堆中移除后，与二叉树的删除使用左右子树的最值子节点替换类似，对移除位置使用堆数组最后位置元素替换到移除位置上，然后重新平衡二叉堆。

假设使用最大优先队列即父节点大于或等于子节点

当数组最后一个元素被替换到删除位置时，这个叶子节点元素key必定小于删除位置的父节点p，所以需要与较大的子节点child比较

• 如果节点key < 较大的子节点child，交换key与child的位置，并继续与新的较大子节点比较
• 如果节点key >= 较大的子节点child，完成当前堆有序

如果节点key交换到了叶子节点k<half即堆中最后一个父节点为half=size/2（数组下标从0开始 1也一样），此时不再需要向下比较

下面是PriorityQueue的源码（最小优先队列为例，如果是最大优先队列需要交换符号）

// 将指定元素在堆中位置为k的向下使堆有序
private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
    // assert n > 0;
    Comparable<? super T> key = (Comparable<? super T>)x;
    // 表示非叶子节点的最后一个节点下标
    int half = n >>> 1;           // loop while a non-leaf
    while (k < half) {
        // k的左子节点
        int child = (k << 1) + 1; // assume left child is least
        Object c = es[child];
        int right = child + 1;
        // 如果两个子节点right更小则使用right节点比较
        if (right < n &&
            ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
            c = es[child = right];
        if (key.compareTo((T) c) <= 0)
            break;
        // 将子节点c上移
        es[k] = c;
        k = child;
    }
    // key向下移动到k位置
    es[k] = key;
}

在向下筛选时，叶子节点不需要再向下比较筛选，所以比较完最后一个父节点size/2 -1后（(size/2)-1 < size/2），退出循环

二叉堆有序的关键在于堆数组的元素的位置，在使堆有序的时候经常要使用父子节点和最后一个父节点的位置

实现

构造器

构造器需要对堆数组和可能指定的比较器comparator初始化，还有如果使用集合初始化PriorityQueue时需要考虑集合是否有序。

下面使用两个典型的构造器说明，其他的构造器调用或调用相同的方法

一般初始化

• PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

/**
    * Creates a {@code PriorityQueue} with the specified initial capacity
    * that orders its elements according to the specified comparator.
    *
    * @param  initialCapacity the initial capacity for this priority queue
    * @param  comparator the comparator that will be used to order this
    *         priority queue.  If {@code null}, the {@linkplain Comparable
    *         natural ordering} of the elements will be used.
    * @throws IllegalArgumentException if {@code initialCapacity} is
    *         less than 1
    */
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
    //至少容量为1是为了兼容性
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}

集合初始化

• PriorityQueue(Collection<? extends E> c)

/**
    * Creates a {@code PriorityQueue} containing the elements in the
    * specified collection.  If the specified collection is an instance of
    * a {@link SortedSet} or is another {@code PriorityQueue}, this
    * priority queue will be ordered according to the same ordering.
    * Otherwise, this priority queue will be ordered according to the
    * {@linkplain Comparable natural ordering} of its elements.
    *
    * @param  c the collection whose elements are to be placed
    *         into this priority queue
    * @throws ClassCastException if elements of the specified collection
    *         cannot be compared to one another according to the priority
    *         queue's ordering
    * @throws NullPointerException if the specified collection or any
    *         of its elements are null
    */
@SuppressWarnings("unchecked")
public PriorityQueue(Collection<? extends E> c) {
    // 如果是SortedSet
    if (c instanceof SortedSet<?>) {
        SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
        this.comparator = (Comparator<? super E>) ss.comparator();
        // 从集合中初始化到堆数组中 检查集合元素是否存在null 由于本身是有序的 queue[0]一定是最值 不需要使堆完全有序
        initElementsFromCollection(ss);
    }
    // 如果是优先队列
    else if (c instanceof PriorityQueue<?>) {
        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        // 直接使用PriorityQueue.toArray的数组 堆完整有序
        initFromPriorityQueue(pq);
    }
    else {
        this.comparator = null;
        // 将指定的集合添加到priorityqueue中并使堆有序
        initFromCollection(c);
    }
}

通过集合初始化涉及到的私有方法实现：

// 从指定集合Collection中 初始化堆数组  此时堆数组无序
private void initElementsFromCollection(Collection<? extends E> c) {
    Object[] a = c.toArray();
    // If c.toArray incorrectly doesn't return Object[], copy it.
    // 保证底层数组queue为Object[]类型
    if (a.getClass() != Object[].class)
        a = Arrays.copyOf(a, a.length, Object[].class);
    int len = a.length;
    // 如果有比较器 扫描容器数组中元素不含null元素
    if (len == 1 || this.comparator != null)
        for (int i = 0; i < len; i++)
            if (a[i] == null)
                throw new NullPointerException();
    this.queue = a;
    this.size = a.length;
}

/**
    * Initializes queue array with elements from the given Collection.
    *
    * @param c the collection
    */
// 将指定的集合添加到priorityqueue中并使堆有序
private void initFromCollection(Collection<? extends E> c) {
    // 将集合元素初始化到优先队列queue中
    initElementsFromCollection(c);
    // 使堆有序
    heapify();
}

// 如果是PriorityQueue就直接使用toArray的数组 否则调用initFromCollection
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
    if (c.getClass() == PriorityQueue.class) {
        this.queue = c.toArray();
        this.size = c.size();
    } else {
        initFromCollection(c);
    }
}

注意

• 优先队列创建的堆数组最小为1，默认构造器创建的大小为11，在容量不够时自动扩容
• 通过集合初始化时需要考虑原来集合是否有序，如果原来集合有序，即保证堆有序，而下标0的元素一定是最值。

下面使用一个有序集合构造为优先队列的示例说明 有序数组本就堆有序

    static void constructoraddAllTest() {
        SortedSet<Integer> set = new TreeSet<>();
        set.addAll(Arrays.asList(1, 3, 6, 7, 9, 12, 15));
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(set);
        System.out.println("before:" + Arrays.toString(queue.queue));
        System.out.println("after:");
        while (queue.poll() != null) {
            System.out.println(Arrays.toString(queue.queue));
        }
/*输出：
before:[1, 3, 6, 7, 9, 12, 15]
after:
[3, 7, 6, 15, 9, 12, null]
[6, 7, 12, 15, 9, null, null]
[7, 9, 12, 15, null, null, null]
[9, 15, 12, null, null, null, null]
[12, 15, null, null, null, null, null]
[15, null, null, null, null, null, null]
[null, null, null, null, null, null, null]

*/
    }

下面是模拟堆数组第一次出队的步骤：

经过集合构造器的堆数组：    [1, 3, 6, 7, 9, 12, 15]

                            1               <--出队
                    3               6
                7       9       12      15  <--到堆顶替换
            --------------------------------    
                            15              <--用数组最后元素替换
                    3               6
                7       9       12      
            --------------------------------
                            3
                    15              6       <--下沉　取子节点中小的交换
                7       9       12
            --------------------------------
                            3
                    7               6
                15      9       12          <--完成下沉　
            --------------------------------
        一次出队后堆数组：   [3, 7, 6, 15, 9, 12, null]      

• 通过构造器构造的堆数组一定时堆有序的。不存在在插入删除时才有序，如果一开始堆数组不保证顺序，插入仅下沉和删除仅上浮不可能保证队头是最值了

扩容

    /**
     * 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%
        // 如果数组过小(<64)就扩大两倍，否则扩大一半50%
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // overflow-conscious code
        // 如果增加50%后超过最大容量，没有溢出就使用int最大或最大容量值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 复制到新数组长度为newCapaciry
        queue = Arrays.copyOf(queue, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

PriorityQueue的扩容比较简单，当数组较小时(<64)扩大为数组的两倍，否则将扩大50%

添加

/**
    * 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)
        // i + 1用于判断是否溢出，当容量达到int和vm的限制时才有影响。i+1不会用于扩容容量size
        grow(i + 1);
    // 插入数组已有元素最后然后向上有序，i为最新位置
    siftUp(i, e);
    size = i + 1;
    return true;
}

注意

• 优先队列不允许插入null元素
• 优先队列先执行扩容操作才将元素插入新数组。即在扩容前堆数组可能装满元素
• 插入新元素后需要在堆向上筛选使堆有序

移除

移除第一个（最小）元素。使用最后一个元素替代位置0并下沉有序

public E poll() {
    final Object[] es;
    final E result;
    // 如果数组第一个元素不为null
    if ((result = (E) ((es = queue)[0])) != null) {
        modCount++;
        final int n;
        // 最后一个元素
        final E x = (E) es[(n = --size)];
        es[n] = null;
        // 还存在元素，使堆有序
        if (n > 0) {
            // 将位置0的元素下沉使堆有序
            final Comparator<? super E> cmp;
            if ((cmp = comparator) == null)
                siftDownComparable(0, x, es, n);
            else
                siftDownUsingComparator(0, x, es, n, cmp);
        }
    }
    return result;
}

移除任意位置的元素i。

• 判断i是否为最后一个元素，是则置为null即可

• 将最后一个元素l覆盖移除位置i，元素l的大小与i的父子节点不确定，不能简单的仅siftDown就认为堆有序

  • 执行siftDown操作，假定元素l>i的子节点们，如果操作成功该位置不再是元素l，否则
  • 执行siftUp操作，假定元素l<i的父节点，如果操作成功元素l将上移，否则
  • 不需要移动元素，刚好堆有序，元素 i的子节点<=l<=i的父节点

/**
    * Removes a single instance of the specified element from this queue,
    * if it is present.  More formally, removes an element {@code e} such
    * that {@code o.equals(e)}, if this queue contains one or more such
    * elements.  Returns {@code true} if and only if this queue contained
    * the specified element (or equivalently, if this queue changed as a
    * result of the call).
    *
    * @param o element to be removed from this queue, if present
    * @return {@code true} if this queue changed as a result of the call
    */
public boolean remove(Object o) {
    int i = indexOf(o);
    if (i == -1)
        return false;
    else {
        removeAt(i);
        return true;
    }
}

/**
    * Removes the ith element from queue.
    *
    * Normally this method leaves the elements at up to i-1,
    * inclusive, untouched.  Under these circumstances, it returns
    * null.  Occasionally, in order to maintain the heap invariant,
    * it must swap a later element of the list with one earlier than
    * i.  Under these circumstances, this method returns the element
    * that was previously at the end of the list and is now at some
    * position before i. This fact is used by iterator.remove so as to
    * avoid missing traversing elements.
    */
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;
        // 将最后一个元素覆盖被移除的位置i并下沉
        siftDown(i, moved);
        // 无法下沉，未修改堆结构
        if (es[i] == moved) {
            // 上浮操作
            siftUp(i, moved);
            // 上浮成功，返回该对象，用于iterator遍历，forget me not
            if (es[i] != moved)
                return moved;
        }
    }
    // 正常情况下都返回null，仅当迭代时被修改返回
    return null;
}

注意

removeAt返回moved对象，表示移除时最后一个元素被替换移除位置时被siftUp成功的元素，对于迭代器来说是致命的，无法保证元素正确被遍历，未遍历的元素（最后一个）已经被移动到已经遍历过的位置。

返回该元素遍历，由于移除的关系，最后元素i已经不会被获取，所以提前返回该元素

                            1               
                    6               3
删除12-->     12          15      7       4   <--最后元素用于替换
            -------------------------------

                            1               
                    6               3
需要上浮-->     4       15      7
            -------------------------------
                            1               
                    4               3
   完成       6       15      7
            -------------------------------

获取

// 返回但不移除 队头元素
public E peek() {
    return (E) queue[0];
}

迭代器

    /**
     * Returns an iterator over the elements in this queue. The iterator
     * does not return the elements in any particular order.
     *
     * @return an iterator over the elements in this queue
     */
    public Iterator<E> iterator() {
        return new Itr();
    }

    private final class Itr implements Iterator<E> {
        /**
         * Index (into queue array) of element to be returned by
         * subsequent call to next.
         */
        // 下一个调用返回的元素下标
        private int cursor = 0;

        /**
         * Index of element returned by most recent call to next,
         * unless that element came from the forgetMeNot list.
         * Set to -1 if element is deleted by a call to remove.
         */
        private int lastRet = -1;

        /**
         * A queue of elements that were moved from the unvisited portion of
         * the heap into the visited portion as a result of "unlucky" element
         * removals during the iteration.  (Unlucky element removals are those
         * that require a siftup instead of a siftdown.)  We must visit all of
         * the elements in this list to complete the iteration.  We do this
         * after we've completed the "normal" iteration.
         *
         * We expect that most iterations, even those involving removals,
         * will not need to store elements in this field.
         */
        /*
         * 由于在迭代器中删除堆数组中的某个元素，在使用堆数组中最后一个元素替换时,该元素比删除元素
         * 的父节点更小（默认最小堆），会使该元素上浮(siftUp)导致该元素替换到已经遍历过的位置，
         * 此时使用deque存储该元素并在最后再遍历
         */
        private ArrayDeque<E> forgetMeNot = null;

        /**
         * Element returned by the most recent call to next iff that
         * element was drawn from the forgetMeNot list.
         */
        // 在遍历forgetMeNot时保存最近访问的元素
        private E lastRetElt = null;

        /**
         * The modCount value that the iterator believes that the backing
         * Queue should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        private int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor < size ||
                (forgetMeNot != null && !forgetMeNot.isEmpty());
        }

        @SuppressWarnings("unchecked")
        public E next() {
            if (expectedModCount != modCount)
                throw new ConcurrentModificationException();
            // 以堆数组的顺序 返回下一个元素 即迭代器不保证优先队列的顺序
            if (cursor < size)
                return (E) queue[lastRet = cursor++];
            // 如果有unlucky元素 就遍历
            if (forgetMeNot != null) {
                lastRet = -1;
                lastRetElt = forgetMeNot.poll();
                if (lastRetElt != null)
                    return lastRetElt;
            }
            // 如果cursor >= size或 forgetmenot为空返回null
            throw new NoSuchElementException();
        }

        public void remove() {
            if (expectedModCount != modCount)
                throw new ConcurrentModificationException();
            // 正常next后删除
            if (lastRet != -1) {
                // 删除最近的访问元素  接受可能的unlucky元素
                E moved = PriorityQueue.this.removeAt(lastRet);
                lastRet = -1;
                // 删除正常 无unlucky元素
                if (moved == null)
                    cursor--;
                // 存在unlucky元素 添加进入forgetNot队列
                else {
                    if (forgetMeNot == null)
                        forgetMeNot = new ArrayDeque<>();
                    forgetMeNot.add(moved);
                }
            }
            // 如果是在遍历forgetMeNot时调用remove
            else if (lastRetElt != null) {
                // 删除最近遍历的forgetMeNot的元素
                PriorityQueue.this.removeEq(lastRetElt);
                lastRetElt = null;
            } else {
                throw new IllegalStateException();
            }
            expectedModCount = modCount;
        }
    }

注意

• PriorityQueue的迭代器不保证顺序遍历 ，在需要顺序遍历时请使用Arrays.sort(pq.toArray())

• 迭代器是在堆数组中一个个遍历，无法保证优先队列的顺序；

• 由于个别元素的特殊性，在删除元素时替换元素上浮，导致已经遍历的位置替换为新元素，所以这样的元素均放置在一个deque中，priorityqueue遍历完成后再遍历deque，无法保证顺序

---

并行迭代器Spliterator

---

参考

• openjdk-11
• 2.4 Priority Queues