二叉堆
堆有序：当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。根结点是堆有序的二叉树中的最大节点。
二叉堆：二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按层级存储（不使用数组的第一个位置）。
二叉堆可以使用数组或者二叉树实现，在这里使用数组实现。在数组中，根结点放置在下标为1的空间内；下标k的结点的父结点的下标为?k?，它的两个子结点的下标为2k和2k+1.
代码实现：
构造堆的过程中，肯定会用到比较方法和交换方法：
//比较方法
private boolean less(int i,int j)
{ return pq.[i].compareTo(pq[j])<0; }
//交换方法
priivate void exch(int i,intj)
{ Key t = pq[i]; pq[i] = pq[j]; pq[j] = t; }在对堆进行有序化的过程中会遇到两种情况：
- 当某个节点优先级上升(或在堆底加入了一个新元素)时，我们需要由下至上恢复堆的顺序；
- 当某个节点优先级下降(例如将根结点替换为一个较小节点)时，我们需要由上至下恢复堆的顺序；
我们把由下至上恢复堆的顺序称为上浮，把由上至下恢复堆的顺序叫下沉。
上浮操作：
private void swim(int k){while(k>1 && less(k/2,k){exch(k/2,k);k=k/2;}
}下沉操作：
private void sink(int k){while(2*k <= N){int j = 2*k;if(j<N && less(j,j+1)) j++; //保证j是k两个子节点中的较小者if(!less(k,j)) break; //如果k大于j，结束exch(k,j);k = j;}
}通过使用上面的方法，我们就可以构造出一个堆，堆的插入操作和删除最大元素操作都可以在对数级别的时间内完成。
- 插入元素：我们将新元素插入数组末尾，增加堆的大小并让新元素上浮到正确位置；
- 删除最大元素：我们从数组顶端删去最大元素并将数组末尾元素置入顶端，下沉它到正确位置。
优先权队列
优先权队列的功能就是插入元素和删除最大元素，所以我们完全可以基于堆来实现优先权队列。
明白堆和上面的代码，优先权队列很容易实现，直接来看代码：
public class MaxPQ<Key extends Comparable<Key>>{private Key[] pq; //基于堆private int N; //堆的大小public MaxPQ(int maxN){ pq = (Key[]) new Comparable[maxN+1]; }public void insert(Key v){pq[++] = v;swim(N); //恢复堆的有序性}public Key delMax(){public Key max = pq[1];exch(1,N--); //和最后一个节点交换pq[N-1] = null; //防止对象游离sink(1); //恢复堆的有序性return max;
}
//less()、exch()、swim()、sink()方法见上文
}