堆简介
Java中PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示。
前面以Java ArrayDeque为例讲解了Stack和Queue，其实还有一种特殊的队列叫做PriorityQueue，即优先队列。优先队列的作用是能保证每次取出的元素都是队列中权值最小的（Java的优先队列每次取最小元素，C++的优先队列每次取最大元素）。这里牵涉到了大小关系，元素大小的评判可以通过元素本身的自然顺序（natural ordering），也可以通过构造时传入的比较器（Comparator，类似于C++的仿函数）。
Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。
二叉堆可以用数组来表示，父子节点下标关系为：
leftIndex = parentIndex * 2 + 1rightIndex = parentIndex * 2 + 2parentIndex = (nodeIndex - 1) / 2 nodeIndex 表示左/右子节点通过上述三个公式，可以轻易计算出某个节点的父节点以及子节点的下标。这也就是为什么可以直接用数组来存储堆的原因。
PriorityQueue 的peek()和element操作是常数时间，add()、 offer()、无参数的remove()以及poll()方法的时间复杂度都是log(N)。
构造器
来看一下源码：
public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable { private static final long serialVersionUID = -7720805057305804111L; private static final int DEFAULT_INITIAL_CAPACITY = 11; transient Object[] queue; //用一个数组来实现 private int size = 0; private final Comparator<? super E> comparator; transient int modCount = 0; //无参构造器，初始大小默认为11 public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); } //传初始容量的构造器 public PriorityQueue(int initialCapacity) { this(initialCapacity, null); } //传比较器的构造器 public PriorityQueue(Comparator<? super E> comparator) { this(DEFAULT_INITIAL_CAPACITY, comparator); } //传初始容量、比较器的构造器 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 if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator; } 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); } } public PriorityQueue(PriorityQueue<? extends E> c) { this.comparator = (Comparator<? super E>) c.comparator(); initFromPriorityQueue(c); } }add(E e)和offer(E e)
add(E e)和offer(E e)的语义相同，都是向优先队列中插入元素，只是Queue接口规定二者对插入失败时的处理不同，前者在插入失败时抛出异常，后者则会返回false。但是对于 PriorityQueue 这两个方法其实没什么差别。
public boolean add(E e) { return offer(e); } public boolean offer(E e) { if (e == null) //不允许放入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; }上述代码中，扩容函数grow()类似于ArrayList里的grow()函数，就是再申请一个更大的数组，并将原数组的元素复制过去，这里不再赘述。需要注意的是siftUp(int k, E x)方法，该方法用于插入元素x并维持堆的特性。
新加入的元素x可能会破坏小顶堆的性质，因此需要进行调整。调整的过程为：从k指定的位置开始，将x逐层与当前点的parent进行比较并交换，直到满足x >= queue[parent]为止。注意这里的比较可以是元素的自然顺序，也可以是依靠比较器的顺序。
其源码如下：
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<? 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; } 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; }PriorityQueue.offer(E e) siftUp 过程图解：
element() 和 peek()
element()和peek()的语义完全相同，都是获取但不删除队首元素，也就是队列中权值最小的那个元素，二者唯一的区别是当方法失败时前者抛出异常，后者返回null。根据小顶堆的性质，堆顶那个元素就是全局最小的那个；由于堆用数组表示，根据下标关系，0下标处的那个元素既是堆顶元素。所以直接返回数组0下标处的那个元素即可。
源码如下：
public E peek() { return (size == 0) ? null : (E) queue[0]; }remove() 和 poll()
remove()和poll()方法的语义也完全相同，都是获取并删除队首元素，区别是当方法失败时前者抛出异常，后者返回null。由于删除操作会改变队列的结构，为维护小顶堆的性质，需要进行必要的调整。
删除队首：
public E poll() { if (size == 0) return null; int s = --size; modCount++; E result = (E) queue[0]; //0下标处的那个元素就是最小的那个 E x = (E) queue[s]; queue[s] = null; if (s != 0) siftDown(0, x); //调整 return result; }上述代码首先记录0下标处的元素，并用最后一个元素替换0下标位置的元素，之后调用siftDown()方法对堆进行调整，最后返回原来0下标处的那个元素（也就是最小的那个元素）。重点是siftDown(int k, E x)方法，该方法的作用是从k指定的位置开始，将x逐层向下与当前点的左右孩子中较小的那个交换，直到x小于或等于左右孩子中的任何一个为止。
private void siftDown(int k, E x) { if (comparator != null) siftDownUsingComparator(k, x); else siftDownComparable(k, x); }PriorityQueue.poll() siftDown 过程图解：
remove(Object o)
删除特定元素：
remove(Object o)方法用于删除队列中跟o相等的某一个元素（如果有多个相等，只删除一个），该方法不是Queue接口内的方法，而是Collection接口的方法。由于删除操作会改变队列结构，所以要进行调整；又由于删除元素的位置可能是任意的，所以调整过程比其它函数稍加繁琐。
具体来说，remove(Object o)可以分为2种情况：
删除的是最后一个元素。直接删除即可，不需要调整。删除的不是最后一个元素，从删除点开始以最后一个元素为参照调用一次siftDown()即可。此处不再赘述。PriorityQueue.remove(Object o) 的 2 种情况：
public boolean remove(Object o) { int i = indexOf(o); if (i == -1) return false; else { removeAt(i); return true; } } private int indexOf(Object o) { if (o != null) { for (int i = 0; i < size; i++) if (o.equals(queue[i])) return i; } return -1; } private E removeAt(int i) { // assert i >= 0 && i < size; modCount++; int s = --size; if (s == i) // removed last element queue[i] = null; else { E moved = (E) queue[s]; queue[s] = null; siftDown(i, moved); if (queue[i] == moved) { siftUp(i, moved); if (queue[i] != moved) return moved; } } return null; } boolean removeEq(Object o) { for (int i = 0; i < size; i++) { if (o == queue[i]) { removeAt(i); return true; } } return false; }常用方法时间复杂度总结
方法时间复杂度booean offer(E e)O(log)boolean contains(Object o)O(N)E peek()O(1)E poll()O(log)boolean remove(Object o)O(N)int size()O(1)