PriorityQueue

一個基于優(yōu)先級堆的無界優(yōu)先級隊列。

二叉堆

可視化操作：二叉堆

二叉堆(The binary heap)數(shù)據(jù)結(jié)構(gòu)能夠有效的支持基本的優(yōu)先隊列操作初橘。key存儲在一個數(shù)組中验游，其中每個key大于(或等于)指定的兩個位置及以上的key

如果key節(jié)點比兩個key子節(jié)點（如果有）大或等于表示這個二叉樹是堆有序的。（子節(jié)點間無序）

位置

二叉堆使用完全二叉樹在數(shù)組中實現(xiàn)保檐，堆中節(jié)點的位置可以用數(shù)組下標(biāo)很方便的表示耕蝉。其中k表示數(shù)組下標(biāo)

• 數(shù)組下標(biāo)1開始

一個節(jié)點的父節(jié)點：k/2 向下取整

一個節(jié)點的兩個子節(jié)點：左子節(jié)點2*k 右子節(jié)點2*k+1剑梳。

• 數(shù)組下標(biāo)0開始

父節(jié)點：(k-1)/2 向下取整

左子節(jié)點：2*k+1

右子節(jié)點：2*(k+1) 即 (2*k+1)+1

最后一個父節(jié)點（只有存在子節(jié)點）：(size/2)-1

PriorityQueue為下標(biāo)0開始

上付ｖā（siftUp）

當(dāng)一個key被添加到有序的二叉堆時姥宝，即插入到數(shù)組最后廊酣，此時會破壞堆的有序性湾盒，需要交換key使堆有序帚屉。假設(shè)使用最大優(yōu)先隊列即父節(jié)點大于或等于子節(jié)點

過程很簡單捡遍，即比較key與父節(jié)點p位置為(k-1)/2的大戌志尽：（針對最大優(yōu)先隊列砸王，如果是最小優(yōu)先推盛，顛倒符號即可）

• 如果key>p就交換兩者的位置并與新的父節(jié)點繼續(xù)比較
• 如果key<=p排序完成

下面是PriorityQueue的源碼，注意是使用 最小堆谦铃，即自然順序natural ordering

// 使用指定位置k的節(jié)點x向上使堆有序
private static <T> void siftUpComparable(int k, T x, Object[] es) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    // 找到key在堆中的位置  當(dāng)key的位置k是根節(jié)點位置0時終止
    while (k > 0) {
        // k位置的父節(jié)點位置
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        // 如果key比父節(jié)點大或相等時 此時堆有序 最小堆
        if (key.compareTo((T) e) >= 0)
            break;
        // 將父節(jié)點e移動到子節(jié)點位置k上耘成。此時會導(dǎo)致父子節(jié)點都為同一個值原來的父節(jié)點，子節(jié)點被覆蓋
        es[k] = e;
        k = parent;
    }
    // 將key放到父節(jié)點位置k驹闰。
    es[k] = key;
}

下沉（siftDown）

在堆中移除后瘪菌，與二叉樹的刪除使用左右子樹的最值子節(jié)點替換類似，對移除位置使用堆數(shù)組最后位置元素替換到移除位置上嘹朗，然后重新平衡二叉堆师妙。

假設(shè)使用最大優(yōu)先隊列即父節(jié)點大于或等于子節(jié)點

當(dāng)數(shù)組最后一個元素被替換到刪除位置時，這個葉子節(jié)點元素key必定小于刪除位置的父節(jié)點p屹培，所以需要與較大的子節(jié)點child比較

• 如果節(jié)點key < 較大的子節(jié)點child默穴，交換key與child的位置，并繼續(xù)與新的較大子節(jié)點比較
• 如果節(jié)點key >= 較大的子節(jié)點child褪秀，完成當(dāng)前堆有序

如果節(jié)點key交換到了葉子節(jié)點k<half即堆中最后一個父節(jié)點為half=size/2（數(shù)組下標(biāo)從0開始 1也一樣）蓄诽，此時不再需要向下比較

下面是PriorityQueue的源碼（最小優(yōu)先隊列為例，如果是最大優(yōu)先隊列需要交換符號）

// 將指定元素在堆中位置為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;
    // 表示非葉子節(jié)點的最后一個節(jié)點下標(biāo)
    int half = n >>> 1;           // loop while a non-leaf
    while (k < half) {
        // k的左子節(jié)點
        int child = (k << 1) + 1; // assume left child is least
        Object c = es[child];
        int right = child + 1;
        // 如果兩個子節(jié)點right更小則使用right節(jié)點比較
        if (right < n &&
            ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
            c = es[child = right];
        if (key.compareTo((T) c) <= 0)
            break;
        // 將子節(jié)點c上移
        es[k] = c;
        k = child;
    }
    // key向下移動到k位置
    es[k] = key;
}

在向下篩選時媒吗，葉子節(jié)點不需要再向下比較篩選仑氛，所以比較完最后一個父節(jié)點size/2 -1后（(size/2)-1 < size/2），退出循環(huán)

二叉堆有序的關(guān)鍵在于堆數(shù)組的元素的位置，在使堆有序的時候經(jīng)常要使用父子節(jié)點和最后一個父節(jié)點的位置

實現(xiàn)

構(gòu)造器

構(gòu)造器需要對堆數(shù)組和可能指定的比較器comparator初始化锯岖，還有如果使用集合初始化PriorityQueue時需要考慮集合是否有序介袜。

下面使用兩個典型的構(gòu)造器說明，其他的構(gòu)造器調(diào)用或調(diào)用相同的方法

一般初始化

• 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();
        // 從集合中初始化到堆數(shù)組中 檢查集合元素是否存在null 由于本身是有序的 queue[0]一定是最值 不需要使堆完全有序
        initElementsFromCollection(ss);
    }
    // 如果是優(yōu)先隊列
    else if (c instanceof PriorityQueue<?>) {
        PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
        this.comparator = (Comparator<? super E>) pq.comparator();
        // 直接使用PriorityQueue.toArray的數(shù)組 堆完整有序
        initFromPriorityQueue(pq);
    }
    else {
        this.comparator = null;
        // 將指定的集合添加到priorityqueue中并使堆有序
        initFromCollection(c);
    }
}

通過集合初始化涉及到的私有方法實現(xiàn)：

// 從指定集合Collection中 初始化堆數(shù)組  此時堆數(shù)組無序
private void initElementsFromCollection(Collection<? extends E> c) {
    Object[] a = c.toArray();
    // If c.toArray incorrectly doesn't return Object[], copy it.
    // 保證底層數(shù)組queue為Object[]類型
    if (a.getClass() != Object[].class)
        a = Arrays.copyOf(a, a.length, Object[].class);
    int len = a.length;
    // 如果有比較器 掃描容器數(shù)組中元素不含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) {
    // 將集合元素初始化到優(yōu)先隊列queue中
    initElementsFromCollection(c);
    // 使堆有序
    heapify();
}

// 如果是PriorityQueue就直接使用toArray的數(shù)組 否則調(diào)用initFromCollection
private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
    if (c.getClass() == PriorityQueue.class) {
        this.queue = c.toArray();
        this.size = c.size();
    } else {
        initFromCollection(c);
    }
}

注意

• 優(yōu)先隊列創(chuàng)建的堆數(shù)組最小為1嚎莉，默認構(gòu)造器創(chuàng)建的大小為11米酬，在容量不夠時自動擴容
• 通過集合初始化時需要考慮原來集合是否有序沛豌，如果原來集合有序趋箩，即保證堆有序，而下標(biāo)0的元素一定是最值加派。

下面使用一個有序集合構(gòu)造為優(yōu)先隊列的示例說明 有序數(shù)組本就堆有序

    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]

*/
    }

下面是模擬堆數(shù)組第一次出隊的步驟：

經(jīng)過集合構(gòu)造器的堆數(shù)組：    [1, 3, 6, 7, 9, 12, 15]

                            1               <--出隊
                    3               6
                7       9       12      15  <--到堆頂替換
            --------------------------------    
                            15              <--用數(shù)組最后元素替換
                    3               6
                7       9       12      
            --------------------------------
                            3
                    15              6       <--下沉　取子節(jié)點中小的交換
                7       9       12
            --------------------------------
                            3
                    7               6
                15      9       12          <--完成下沉　
            --------------------------------
        一次出隊后堆數(shù)組：   [3, 7, 6, 15, 9, 12, null]      

• 通過構(gòu)造器構(gòu)造的堆數(shù)組一定時堆有序的叫确。不存在在插入刪除時才有序，如果一開始堆數(shù)組不保證順序芍锦，插入僅下沉和刪除僅上浮不可能保證隊頭是最值了

擴容

    /**
     * Increases the capacity of the array.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // 舊數(shù)組容量
        int oldCapacity = queue.length;
        // Double size if small; else grow by 50%
        // 如果數(shù)組過小(<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);
        // 復(fù)制到新數(shù)組長度為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的擴容比較簡單娄琉，當(dāng)數(shù)組較小時(<64)擴大為數(shù)組的兩倍次乓，否則將擴大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用于判斷是否溢出，當(dāng)容量達到int和vm的限制時才有影響孽水。i+1不會用于擴容容量size
        grow(i + 1);
    // 插入數(shù)組已有元素最后然后向上有序票腰，i為最新位置
    siftUp(i, e);
    size = i + 1;
    return true;
}

注意

• 優(yōu)先隊列不允許插入null元素
• 優(yōu)先隊列先執(zhí)行擴容操作才將元素插入新數(shù)組。即在擴容前堆數(shù)組可能裝滿元素
• 插入新元素后需要在堆向上篩選使堆有序

移除

移除第一個（最信）元素杏慰。使用最后一個元素替代位置0并下沉有序

public E poll() {
    final Object[] es;
    final E result;
    // 如果數(shù)組第一個元素不為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的父子節(jié)點不確定谒主，不能簡單的僅siftDown就認為堆有序

  • 執(zhí)行siftDown操作朝扼，假定元素l>i的子節(jié)點們，如果操作成功該位置不再是元素l霎肯，否則
  • 執(zhí)行siftUp操作擎颖，假定元素l<i的父節(jié)點，如果操作成功元素l將上移姿现，否則
  • 不需要移動元素肠仪，剛好堆有序，元素 i的子節(jié)點<=l<=i的父節(jié)點

/**
    * 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);
        // 無法下沉备典，未修改堆結(jié)構(gòu)
        if (es[i] == moved) {
            // 上浮操作
            siftUp(i, moved);
            // 上浮成功异旧，返回該對象，用于iterator遍歷提佣，forget me not
            if (es[i] != moved)
                return moved;
        }
    }
    // 正常情況下都返回null吮蛹，僅當(dāng)?shù)鷷r被修改返回
    return null;
}

注意

removeAt返回moved對象荤崇，表示移除時最后一個元素被替換移除位置時被siftUp成功的元素，對于迭代器來說是致命的潮针，無法保證元素正確被遍歷术荤，未遍歷的元素（最后一個）已經(jīng)被移動到已經(jīng)遍歷過的位置。

返回該元素遍歷每篷，由于移除的關(guān)系瓣戚，最后元素i已經(jīng)不會被獲取，所以提前返回該元素

                            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.
         */
        // 下一個調(diào)用返回的元素下標(biāo)
        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.
         */
        /*
         * 由于在迭代器中刪除堆數(shù)組中的某個元素焦读，在使用堆數(shù)組中最后一個元素替換時,該元素比刪除元素
         * 的父節(jié)點更凶涌狻（默認最小堆），會使該元素上浮(siftUp)導(dǎo)致該元素替換到已經(jīng)遍歷過的位置矗晃，
         * 此時使用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();
            // 以堆數(shù)組的順序 返回下一個元素 即迭代器不保證優(yōu)先隊列的順序
            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時調(diào)用remove
            else if (lastRetElt != null) {
                // 刪除最近遍歷的forgetMeNot的元素
                PriorityQueue.this.removeEq(lastRetElt);
                lastRetElt = null;
            } else {
                throw new IllegalStateException();
            }
            expectedModCount = modCount;
        }
    }

注意

• PriorityQueue的迭代器不保證順序遍歷 仑嗅，在需要順序遍歷時請使用Arrays.sort(pq.toArray())

• 迭代器是在堆數(shù)組中一個個遍歷，無法保證優(yōu)先隊列的順序张症；

• 由于個別元素的特殊性仓技，在刪除元素時替換元素上浮，導(dǎo)致已經(jīng)遍歷的位置替換為新元素俗他，所以這樣的元素均放置在一個deque中脖捻，priorityqueue遍歷完成后再遍歷deque，無法保證順序

并行迭代器Spliterator

參考

• openjdk-11
• 2.4 Priority Queues