java数据结构－利用Heap（堆）实现PriorityQueue（优先队列）
（一）、首先介绍下优先队列的性质（选自 JDK API）
优先队列是一个基于优先级堆的无界优先级队列。优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的 Comparator 进行排序，具体取决于所使用的构造方法。优先级队列不允许使用 null 元素。依靠自然顺序的优先级队列还不允许插入不可比较的对象（这样做可能导致 ClassCastException）。
此队列的头 是按指定排序方式确定的最小 元素。如果多个元素都是最小值，则头是其中一个元素——选择方法是任意的。队列获取操作 poll、remove、peek 和 element 访问处于队列头的元素。
优先级队列是无界的，但是有一个内部容量，控制着用于存储队列元素的数组大小。它通常至少等于队列的大小。随着不断向优先级队列添加元素，其容量会自动增加。无需指定容量增加策略的细节。
此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选 方法。方法 iterator() 中提供的迭代器不 保证以任何特定的顺序遍历优先级队列中的元素。如果需要按顺序遍历，请考虑使用 Arrays.sort(pq.toArray())。
（二）、优先队列中的二叉堆的实现
从（一）可得知，优先队列是至少允许插入和删除最小者这两个操作的数据结构。
其中，对于优先队列的实现，二叉堆是很常见的。
堆是一棵被完全填满的二叉树，可能例外是底层，底层上的元素从左到右依次填入。
而且如果使用数组表示二叉堆，那么对于数组上的任意位置i上的元素，其左儿子的位置是2i，右儿子在左儿子后的单元（2i +1）中，他的父亲则在位置[i/2]上。
堆的性质，在堆中，对于每一个节点X，X的父亲中的关键字小于或者等于X中的关键字，根节点除外。其中根节点是堆中关键字最小的元素。所以二叉堆的最小元可以在根处找到。
上滤策略为，现在空闲位置创建一个空穴，如果X可以放在空穴中而不破坏堆排序，那么插入完成，否则，把空穴的父节点上的元素移入空穴中，这样，空穴就朝着根的方向上行进一步，直到可以插入为止。
附上完全二叉树的一些性质：
如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0, 1, 2, …, n-1，则有以下关系：
1、若i = 0, 则 i 无双亲.
2、若i > 0, 则 i 的双亲为：(i -1)/2.?
3、若2*i+1 < n, 则 i 的左子女为 2*i+1，若2*i+2 < n, 则 i 的右子女为2*i+2.
4、若结点编号i为偶数，且i!=0,则左兄弟结点i-1.
5、若结点编号i为奇数，且i!=n-1,则右兄弟结点为i+1.
6、结点i 所在层次为：log2(i+1)+1
优先队列是用的堆排序法，算法主要运用在于插入和删除：
下面的代码为二叉堆的实现
1.package com.bird.six; 2. 3./** 4. * @category 二叉堆的实现 5. * @author Bird 6. * 7. */ 8.public class BinaryHeap { 9. 10. private static final int DEAFAULT_CAPACITY = 100; 11. private int currentSize;//堆中的元素个数 12. private Compare[] array;//存储堆中的元素使用数组存储方式 13. 14. public BinaryHeap(){ 15. this(DEAFAULT_CAPACITY); 16. } 17. 18. public BinaryHeap(int capacity){ 19. currentSize = 0; 20. array = new Compare[capacity+1]; 21. 22. } 23. 24. public boolean isEmpty(){ 25. return currentSize == 0; 26. } 27. 28. public boolean isFull(){ 29. return currentSize == array.length-1; 30. } 31. 32. public void makeEmpty(){ 33. currentSize = 0; 34. } 35. 36. /** 37. * 插入使用“上移”法 38. * @param x 39. */ 40. public void insert(Compare x){ 41. if(isFull()) 42. throw new RuntimeException("溢出"); 43. 44. int hole = ++currentSize; 45. for(; hole >1 && x.compareTo(array[hole/2]) < 0; hole /= 2) 46. array[hole] = array[hole/2]; 47. array[hole] = x; 48. } 49. 50. /** 51. * 使用下溢法进行删除操作 52. * @return 53. */ 54. public Compare deleteMin(){ 55. if(isEmpty()) 56. return null; 57. 58. Compare minItem = array[1]; 59. array[1] = array[currentSize--]; 60. percolateDown(1); 61. 62. return minItem; 63. } 64. 65. private void percolateDown(int hole){ 66. int child = 0; 67. Compare tmp = array[hole]; 68. 69. for(; hole * 2 <= currentSize; hole = child){ 70. child = hole * 2; 71. if(child != currentSize && array[child+1].compareTo(array[child])<0) 72. child++; 73. if(array[child].compareTo(tmp)<0) 74. array[hole] = array[child]; 75. else 76. break; 77. } 78. array[hole] = tmp; 79. } 80.} 81. 82.class Compare implements Comparable<Object>{ 83. 84. public int compareTo(Object o) { 85. return ((Integer)this.compareTo(o)); 86. } 87. 88.} /** * 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. * 优先级队列代表着一个平衡的二叉堆：队列[n]的两个孩子分别是队列[2*n+1]和队列[2*(n+1)]。 *先级队列的元素根据构造队列时提供的 Comparator 进行排序，或者按照其自然顺序进行排序： *如果比较器为空，则堆中的每一个结点n和它的的子节点d，有n<=d。 *如果队列不为空的话，则最小值元素是队列[0]。 */ private transient Object[] queue; /** * 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. * 该优先队列结构改变的次数，要获取更多细节，请看AbstractList。 */ private transient int modCount = 0; /** * Creates a {@code PriorityQueue} with the default initial * capacity (11) that orders its elements according to their * {@linkplain Comparable natural ordering}. * 使用默认的初始容量（11）创建一个 PriorityQueue，并根据其自然顺序对元素进行排序。 */ public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); } /** * Creates a {@code PriorityQueue} with the specified initial * capacity that orders its elements according to their * {@linkplain Comparable natural ordering}. ** 使用指定的初始容量创建一个 优先队列，并根据其自然顺序对元素进行排序 * @param initialCapacity the initial capacity for this priority queue * 初始化的容量 * @throws IllegalArgumentException if {@code initialCapacity} is less * than 1 * 如果容量小于1，则跑出异常IllegalArgumentException */ public PriorityQueue(int initialCapacity) { this(initialCapacity, null); } /** * Creates a {@code PriorityQueue} with the specified initial capacity * that orders its elements according to the specified comparator. *使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器对元素进行排序。 * @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. * 用于对此优先级队列进行排序的比较器。如果该参数为 null，则将使用元素的自然顺序 * @throws IllegalArgumentException if {@code initialCapacity} is * less than 1 * 如果容量小于1，则抛出异常IllegalArgumentException */ 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; } /** * 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. *创建包含指定 collection 中元素的 PriorityQueue。如果指定的 collection 是 SortedSet 的一个实例 *或者是另一个 PriorityQueue，那么此优先级队列将根据相同顺序进行排序。否则，此优先级队列 *将根据元素的自然顺序进行排序。 * @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 * ClassCastException -如果根据 c 的顺序无法比较 c 中的各个元素 * @throws NullPointerException if the specified collection or any * of its elements are null * NullPointerException-如果指定 collection 或任何元素为 null */ public PriorityQueue(Collection<? extends E> c) { initFromCollection(c); if (c instanceof SortedSet) comparator = (Comparator<? super E>) ((SortedSet<? extends E>)c).comparator(); else if (c instanceof PriorityQueue) comparator = (Comparator<? super E>) ((PriorityQueue<? extends E>)c).comparator(); else { comparator = null; heapify(); } } /** * Creates a {@code PriorityQueue} containing the elements in the * specified priority queue. This priority queue will be * ordered according to the same ordering as the given priority * queue. *创建包含指定优先级队列元素的 PriorityQueue。此优先级队列将根据与给定优先级队列 *相同的顺序进行排序。 * into this priority queue * 有序 set，其元素将置于此优先级队列中 * @throws ClassCastException if elements of {@code c} cannot be * compared to one another according to {@code c}'s * ordering * ClassCastException -如果根据 c 的顺序无法比较 c 中的各个元素 * @throws NullPointerException if the specified priority queue or any * of its elements are null * NullPointerException-如果指定优先级队列或任何元素为 null */ public PriorityQueue(PriorityQueue<? extends E> c) { comparator = (Comparator<? super E>)c.comparator(); initFromCollection(c); } /** * Creates a {@code PriorityQueue} containing the elements in the * specified sorted set. This priority queue will be ordered * according to the same ordering as the given sorted set. *创建包含指定有序 set 元素的 PriorityQueue。此优先级队列将根据与给定有序 set 相同的顺序进行排序。 参数： * @param c the sorted set whose elements are to be placed * into this priority queue * 有序 set，其元素将置于此优先级队列中 * @throws ClassCastException if elements of the specified sorted * set cannot be compared to one another according to the * sorted set's ordering * ClassCastException - 如果根据有序 set 的顺序无法比较该有序 set 中的各个元素 * @throws NullPointerException if the specified sorted set or any * of its elements are null * NullPointerException - 如果指定有序 set 或任何元素为 null */ public PriorityQueue(SortedSet<? extends E> c) { comparator = (Comparator<? super E>)c.comparator(); initFromCollection(c); }/***将指定的元素插入此优先级队列。/public boolean offer(E e) { //如果加入的元素为空，则抛出异常 if (e == null) throw new NullPointerException(); modCount++; int i = size; //如果要插入的坐标大于队列长度，队列长度加1 if (i >= queue.length) grow(i + 1); size = i + 1; //插入元素 if (i == 0) queue[0] = e; else siftUp(i, e); return true; }//获取并移除此队列的头，如果此队列为空，则返回 null。 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 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; }……