源碼來自jdk1.8

PriorityQueue內(nèi)部由最小堆實(shí)現(xiàn)，也就是說每次執(zhí)行add或是remove之后，總是讓最小的元素移動到根，但是，使用迭代器進(jìn)行訪問時(shí)，不會保證一個(gè)遞增的順序。

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

為了維持最小堆，隊(duì)列的元素類型必須實(shí)現(xiàn)Comparable接口，或者是在構(gòu)造隊(duì)列的時(shí)候提供一個(gè)元素類型的比較器（Comparator），所以元素不能為空。

隊(duì)列的訪問操作poll, remove, peek, and element訪問的是隊(duì)頭元素，在這里也就是根元素，也就是最小的元素。

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

    private static final int DEFAULT_INITIAL_CAPACITY = 11;

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

    /**
     * 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; // non-private to simplify nested class access
    // 省略了方法
}

這里用了一個(gè)Object[]來存放元素，queue[n] 的孩子節(jié)點(diǎn)是 queue[2*n+1] 和 queue[2*(n+1)]

構(gòu)造函數(shù)

PriorityQueue的構(gòu)造函數(shù)大致分為兩類，一種是確定數(shù)組初始化大小和Comparator，另一種是由Collection對象構(gòu)造

public PriorityQueue(Collection<? extends E> c) {
        if (c instanceof SortedSet<?>) {
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            initElementsFromCollection(ss);
        }
        else if (c instanceof PriorityQueue<?>) {
            PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            initFromPriorityQueue(pq);
        }
        else {
            this.comparator = null;
            initFromCollection(c);
        }
    }

可以看到SortedSet和PriorityQueue這兩種在構(gòu)造的時(shí)候可以獲取Comparator（也可能獲取不到，因?yàn)槭亲匀慌判颍?，其余的都是直接?gòu)造，如果這個(gè)對象沒有實(shí)現(xiàn)Comparable接口，那么在使用的時(shí)候就會產(chǎn)生一個(gè)ClassCastException

add/offer

public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        if (i >= queue.length)
            grow(i + 1);
        size = i + 1;
        if (i == 0)
            queue[0] = e;
        else
            siftUp(i, e);
        return true;
    }

add通過offer實(shí)現(xiàn)。這個(gè)函數(shù)干了這幾件事情：檢查為空，增加修改次數(shù)，需要的情況下擴(kuò)展，增加大小，賦值，向上調(diào)整堆，返回真。
這里的關(guān)鍵是SiftUp函數(shù)

private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

將要插入的節(jié)點(diǎn)與父節(jié)點(diǎn)進(jìn)行比較，如果更小，就將父節(jié)點(diǎn)往下，然后繼續(xù)向上比較，如果大于等于，就放在當(dāng)前的位置。

remove()/poll()

注意這里是無參remove，通過poll實(shí)現(xiàn)

public E poll() {
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        E result = (E) queue[0];
        E x = (E) queue[s];
        queue[s] = null;
        if (s != 0)
            siftDown(0, x);
        return result;
    }

刪除并返回最小的隊(duì)頭元素后，將數(shù)組末位的元素放到隊(duì)頭，然后SiftDown，基本于上面相反。

private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        int half = size >>> 1;        // loop while a non-leaf
        while (k < half) {
            int child = (k << 1) + 1; // assume left child is least
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }

將要插入的節(jié)點(diǎn)與兩個(gè)子節(jié)點(diǎn)進(jìn)行比較，如果小于兩個(gè)子節(jié)點(diǎn)，那么就放在當(dāng)前位置，如果大于子節(jié)點(diǎn)，就將較小的子節(jié)點(diǎn)與插入節(jié)點(diǎn)交換，然后在新的位置繼續(xù)向下調(diào)整，直到這個(gè)新的節(jié)點(diǎn)同時(shí)小于兩個(gè)子節(jié)點(diǎn)或者它達(dá)到了一個(gè)葉節(jié)點(diǎn)的位置。