1.概述

?优先级队列的底层实现是基于堆排序
所谓优先级队列，其全局的优先级是通过一步一步访问队头元素之后呈现的，在某一时刻，其队列中的堆从上到下是不严格有序的，这是堆的性质导致的，因为堆只要求父子之间的有序，而不要求兄弟之间的有序。也就是说，队列中出队头元素外的元素们之间在还没有出队时不是严格有序的。其实它们都没有内部排队。
成员：
1. 一个数组 Object[]，名叫queue，用于存放数据，按照完全二叉树的形式，且queue[0]是队头。即 queue[parent]的两个孩子是?queue[2*parent+1]、queue[2*parent+2]
2. 一个比较器 Comparator

2.重要方法解读

2.1 构造函数?

    public PriorityQueue(Collection<? extends E> c) {
        if (c instanceof SortedSet<?>) {
        // code 1
            SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
            this.comparator = (Comparator<? super E>) ss.comparator();
            initElementsFromCollection(ss);
        }
        else if (c instanceof PriorityQueue<?>) {
        // code 2
            PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
            this.comparator = (Comparator<? super E>) pq.comparator();
            initFromPriorityQueue(pq);
        }
        else {
            this.comparator = null;
        // code 3 实际上的初始化方法
            initFromCollection(c);
        }
    }

code1 按照有序集合来初始化
code2 按照优先级队列来初始化，内部直接是把复用引用
code3 是实际的初始化方：保存元素到queue数组中，并“堆化”，后者是优先级队列的“本质”

2.2 方法“堆化”

    private void heapify() {
        // 从倒数第一个非叶子节点开始 siftDown
        for (int i = (size >>> 1) - 1; i >= 0; i--)
            siftDown(i, (E) queue[i]);
    }

    /**
    * 把元素x放到k的位置上。是堆化的原子操作——重要！重要！重要！
    */
    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;
    }

以上是堆排序的对核心的代码，当然也是优先级队列的。
堆化之后，该队就是小顶堆了。下面我们看出队和入队

2.3?出队

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

code1，就是直接返回队头元素 queue[0]
code2，把最后一个元素从队头处插入——注意不是插到队头
siftDown函数在上面已经分析过，就是自伤向下的调整成堆，是堆化的原子操作。

2.4 入队

    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
        // code1 自下往上的调整
            siftUp(i, e);
        return true;
    }

    /**
    * 自下往上的调整。把元素x从位置k插入
    */
    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;
    }