堆有序的·二叉树，就是每个节点值都是大于等于它的子节点值。
这里用大小为N+1的数组pq来表示一个大小为N的堆，不使用pq[0]。
关于二叉树，有一个特点很重要，就是位置k的父节点是k/2，子节点是2*k和2*k+1。
堆的有序化，包括两种情况：
1.当某个节点的值增大时，采用的是由下至上的堆有序化，比较该节点与它的父节点的值，并根据比较结果交换位置。定义方法swim（上浮）。
2.当某个节点的值减小时，采用的是由上至下的堆有序化，比较该节点与它的较大的那个子节点的值，并根据比较结果交换位置。定义方法sink（下沉）。
实现如下：
package MaxPQ; public class MaxPQ<Key extends Comparable<Key>>{ private Key[] pq; private int N= 0; public MaxPQ(int maxN){ pq =(Key[]) new Comparable[maxN+1]; } public boolean isEmpty() { return N==0; } public int size() { return N; } public void insert(Key key) { pq[++N] =key; swim(N); } public Key delMax() { Key re =pq[1]; exch(1,N); pq[N] =null; N--; sink(1); return re; } private void sink(int k) {//由上至下的堆有序化 while (2*k<=N) { int j =2*k; if (less(j,j+1)) { j=j+1; } if (!less(k,j)) { break; } else { exch(k,j); k = j; } } } private void swim(int k) {//由下至上的堆有序化 while (k>1&&less(k/2,k)) { exch(k/2,k); k =k/2; } } private void exch(int i, int j) {//交换第i、j个值 Key key = pq[i]; pq[i] = pq[j]; pq[j] = key; } private boolean less(int i, int j) {//判断第i个值是否比第j个值小 return pq[i].compareTo(pq[j])<0; } }测试如下：
package MaxPQ; public class Test { public static void main(String[] args) { MaxPQ<Integer> m =new MaxPQ<Integer>(11); System.out.println(m.isEmpty()); m.insert(2); m.insert(6); m.insert(4); m.insert(7); m.insert(0); m.insert(8); m.insert(3); m.insert(5); System.out.println(m.size()); System.out.println(m.delMax()); System.out.println(m.delMax()); System.out.println(m.size()); System.out.println(m.isEmpty()); } }
结果如下：
true 8 8 7 6 false
