优先级队列的介绍

优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务。

最小堆性质：除了根以外的所有节点i都有A[PARENT(i)] <= A[i]。PARENT(i)为i节点的父节点索引。

Java中的PriorityQueue

PriorityQueue是从JDK1.5开始提供的新的数据结构接口，一个基于最小堆(完全二叉树、堆排序)的无界优先级队列。特性如下：

1. PriorityQueue中的元素可通过元素的自然排序或者通过队列的构造函数提供一个Comparator对象来排序，如果为自然排序，则入队的元素必须实现Comparable接口，否则会抛出ClassCastException异常。
2. PriorityQueue是不允许null对象入队的。
3. PriorityQueue中的头部元素总是指定排序的最小的元素，如果有多个，则是其中一个。
4. PriorityQueue内部是由一个自动增长的数组来存储元素的，默认初始长度是11。
5. PriorityQueue中的iterator方法不保证以任何特定的顺序遍历队列中的元素，如果需要排序后再遍历，则可以使用Arrays.sort(pq.toArray())。
6. PriorityQueue不是线程安全的，如果要线程安全的使用优先级队列则可以使用PriorityBlockingQueue。

PriorityQueue的结构

PriorityQueue内部成员数组queue其实是实现了一个完全二叉树的数据结构，这棵二叉树的根节点是queue[0]，左子节点是queue[1]，右子节点是queue[2]，而queue[3]又是queue[1]的左子节点，依此类推，给定元素queue[i]，该节点的父节点是queue[(i-1)/2]。因此parent变量就是对应于下标为k的节点的父节点。

入队--O(log(n))

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;    } private void siftUp(int k, E x) {        if (comparator != null)            siftUpUsingComparator(k, x);        else            siftUpComparable(k, x);    }private void siftUpComparable(int k, E x) {        Comparable
     key = (Comparable
    ) 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;    }private void siftUpUsingComparator(int k, E x) {        while (k > 0) {            int parent = (k - 1) >>> 1;            Object e = queue[parent];            if (comparator.compare(x, (E) e) >= 0)                break;            queue[k] = e;            k = parent;        }        queue[k] = x;    }

从源代码角度看，整个入队过程主要做两件事：第一是判别queue数组是否需要扩容；第二是从叶子节点到根节点的排序。

出队--O(log(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;    }private void siftDown(int k, E x) {        if (comparator != null)            siftDownUsingComparator(k, x);        else            siftDownComparable(k, x);    }private void siftDownComparable(int k, E x) {        Comparable
     key = (Comparable
    )x;        int half = size >>> 1;        // 循环至非叶子节点即可，完全二叉树性质：小于size/2的节点必有孩子节点，大于size/2的节点必是叶子节点        while (k < half) {            int child = (k << 1) + 1; // 左孩子节点索引            Object c = queue[child];// 左孩子元素            int right = child + 1;// 右孩子节点索引            if (right < size &&                ((Comparable
    ) 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;    }private void siftDownUsingComparator(int k, E x) {        int half = size >>> 1;        while (k < half) {            int child = (k << 1) + 1;            Object c = queue[child];            int right = child + 1;            if (right < size &&                comparator.compare((E) c, (E) queue[right]) > 0)                c = queue[child = right];            if (comparator.compare(x, (E) c) <= 0)                break;            queue[k] = c;            k = child;        }        queue[k] = x;    }

从源代码角度看，整个出队过程主要做三件事：第一是使用局部变量result保存队头重的元素，以便返回；第二是使用局部变量x保存队尾元素；第三是将队尾元素看作是插入到队头处，然后是从根节点到叶子节点的排序