java自带的优先级队列默认是小顶堆，现在来写一个大顶堆的
目录
实现大顶堆的优先级队列：
importjava.util.NoSuchElementException; classMaxPQ<KeyextendsComparable<Key>> { privateKey[] pq; // 基于堆的完全二叉树privateintN; // 存储在pq[1..N]中，pq[0]没有使用publicMaxPQ(intmaxN) { if (maxN>=0) { pq= (Key[]) newComparable[maxN+1]; } else { thrownewIllegalArgumentException("Illegal Capacity: "+maxN); } } publicMaxPQ() { this(10); } publicbooleanisEmpty() { returnN==0; } publicintsize() { returnN; } publicvoidinsert(Keyv) { if (N==pq.length-1) resize(); pq[++N] =v; swim(N); } publicKeydelete() { // 大顶堆删除最大的if (isEmpty()) thrownewNoSuchElementException("Priority queue underflow"); Keymax=pq[1]; // 从根节点得到最大元素swap(1, N); // 将其和最后一个结点交换pq[N--] =null; // 便于垃圾回收sink(1); // 恢复堆的有序性returnmax; } privatevoidsink(intk) { while ((k<<1) <=N) { // j <= N说明一定有左孩子intj=k<<1; // 左孩子下标if (j<N&&less(j, j+1)) // j < N说明一定有右孩子,如果左孩子小于右孩子的值++j; // 下标转移到右孩子if (!less(k, j)) // 如果k结点的值不小于他的孩子中的最大值break; // 已经无法继续下沉了，跳出swap(k, j); // 下沉，和孩子中的最大值交换k=j; // 现在这个元素已经在刚刚的j位置上，继续记录这个元素的位置，看能否继续下沉 } } privatevoidswim(intk) { // 如果不是第一个元素，并且第k个元素比父节点的值小，那么与父节点交换while (k>1&&less(k>>1, k)) { swap(k>>1, k); k>>=1; } } privatevoidswap(inti, intk) { Keyt=pq[i]; pq[i] =pq[k]; pq[k] =t; } privatebooleanless(inti, intk) { returnpq[i].compareTo(pq[k]) <0; } // ArrayList空参构造方法默认是空数组，第一次插入时会扩容，就比较size+1和10的最大值，扩容后为10privatevoidresize() { // 扩容逻辑简单模仿ArrayListintcapacity=N+ (N>>1); if (capacity<N) // 如果溢出capacity=N; if (capacity>Integer.MAX_VALUE-8) { capacity=hugeCapacity(N); } Key[] temp= (Key[]) newComparable[capacity]; for (inti=1; i<=N; ++i) { // 扩容后复制到新数组temp[i] =pq[i]; } pq=temp; } privateinthugeCapacity(intminCapacity) { if (minCapacity<0) // overflowthrownewOutOfMemoryError(); return (minCapacity>Integer.MAX_VALUE-8) ?Integer.MAX_VALUE : Integer.MAX_VALUE-8; } } publicclassMaxPriorityQueue { publicstaticvoidmain(String[] args) { MaxPQ<Integer>pq=newMaxPQ<Integer>(); pq.insert(5); pq.insert(124); pq.insert(456); pq.insert(678); pq.insert(2); pq.insert(2); pq.insert(6); pq.insert(3); pq.insert(88); pq.insert(-45); pq.insert(99); intsize=pq.size(); for (inti=0; i<size; ++i) { System.out.println(pq.delete()); } } }
运行结果：
678
456
124
99
88
6
5
3
2
2
-45
优先队列由一个基于堆的完全二叉树表示，存储于数组pq[1..N]中，pq[0]没有使用。在insert()中，我们将N加一并把新元素添加在数组最后，然后用swim()恢复堆的有序性（当一颗二叉树的结点都大于等于它的两个子节点时，它被称为堆有序）。在delete()中，我们从pq[1]中得到需要返回的元素，然后将pq[N]移动到pq[1]，将N减一，并用sink()恢复堆有序。同时我们还将不再使用的p[N]设置为null，以便系统回收它所占用的空间。
这里的主要逻辑是：
插入元素insert()：我们将新元素加到数组末尾，增加堆的大小并让这个新元素上浮到合适的位置。
删除最大元素delete()：我们从数组顶端删去最大元素pq[1]，就是先将数组的最后一个元素和顶端元素pq[1]交换，然后减小堆的大小N--(即删除数组最后一个元素)，并让顶端元素下沉到合适的位置。
同理可得：
实现小顶堆的优先级队列：
import java.util.NoSuchElementException; class MinPQ<Key extends Comparable<Key>> { private Key[] pq; // 基于堆的完全二叉树 private int N; // 存储在pq[1..N]中，pq[0]没有使用 public MinPQ(int maxN) { if (maxN >= 0) { pq = (Key[]) new Comparable[maxN + 1]; } else { throw new IllegalArgumentException("Illegal Capacity: " + maxN); } } public MinPQ() { this(10); } public boolean isEmpty() { return N == 0; } public int size() { return N; } public void insert(Key v) { if (N == pq.length - 1) resize(); pq[++N] = v; swim(N); } public Key delete() { // 大顶堆删除最大的 if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); Key max = pq[1]; // 从根节点得到最小元素 swap(1, N); // 将其和最后一个结点交换 pq[N--] = null; // 便于垃圾回收 sink(1); // 恢复堆的有序性 return max; } private void sink(int k) { while ((k << 1) <= N) { // j <= N说明一定有左孩子 int j = k << 1; // 左孩子下标 if (j < N && greater(j, j + 1)) // j < N说明一定有右孩子,如果左孩子大于右孩子的值 ++j; // 下标转移到右孩子 if (!greater(k, j)) // 如果k结点的值不大于他的孩子中的最大值 break; // 已经无法继续下沉了，跳出 swap(k, j); // 下沉，和孩子中的最小值交换 k = j; // 现在这个元素已经在刚刚的j位置上，继续记录这个元素的位置，看能否继续下沉 } } private void swim(int k) { // 如果不是第一个元素，并且第k个元素比父节点的值小，那么与父节点交换 while (k > 1 && greater(k >> 1, k)) { swap(k >> 1, k); k >>= 1; } } private void swap(int i, int k) { Key t = pq[i]; pq[i] = pq[k]; pq[k] = t; } private boolean greater(int i, int k) { return pq[i].compareTo(pq[k]) > 0; } // ArrayList空参构造方法默认是空数组，第一次插入时会扩容，就比较size+1和10的最大值，扩容后为10 private void resize() { // 扩容逻辑简单模仿ArrayList int capacity = N + (N >> 1); if (capacity < N) // 如果溢出 capacity = N; if (capacity > Integer.MAX_VALUE - 8) { capacity = hugeCapacity(N); } Key[] temp = (Key[]) new Comparable[capacity]; for (int i = 1; i <= N; ++i) { // 扩容后复制到新数组 temp[i] = pq[i]; } pq = temp; } private int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > Integer.MAX_VALUE - 8) ? Integer.MAX_VALUE : Integer.MAX_VALUE - 8; } } public class MinPriorityQueue { public static void main(String[] args) { MinPQ<Integer> pq = new MinPQ<Integer>(); pq.insert(5); pq.insert(124); pq.insert(456); pq.insert(678); pq.insert(2); pq.insert(2); pq.insert(6); pq.insert(3); pq.insert(88); pq.insert(-45); pq.insert(99); int size = pq.size(); for (int i = 0; i < size; ++i) { System.out.println(pq.delete()); } } }
运行结果：
-45
2
2
3
5
6
88
99
124
456
678
其实相对于大顶堆的优先级队列就只将less改为了greater。
==========================Talk is cheap, show me the code========================
