定义: 当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序。
定义：二叉堆是一组能够用堆有序的完全二叉树排列的元素，并在数组中按照层级存储（不使用数组的第一个位置）。
<h5> 堆的算法 </h5>
我们用长度为N+1的数组pq[]来表示一个大小为N的堆，不使用pq[0]而将数组元素放在pq[0]至pq[N]中。堆的操作首先会进行一些简单的改动，打破堆的状态，然后再遍历堆将堆的状态恢复。我们称这个过程为堆的有序化。
在有序化的过程中，我们会遇到两种情况。某个结点的优先级上升（或是在堆的底部加入一个新的元素）时，我们要由下至上恢复堆的顺序；当某个结点的优先级下降（例如，将根结点替换为某个较小的元素），我们需要由上至下恢复堆的顺序。
- 由下至上的堆有序化（上浮）：
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(2k <= N){
int j =2k;
if( j<N && less(j, j+1) j++;
if( !less(k,j)) break;
exch(k, j);
k = j;
}
}
基于这两种基本的操作，可以很容易实现插入元素和删除最大元素的操作。
- 插入元素
我们可以将新元素放置在数组末尾，增加堆的大小并让这个新元素上浮到合适的位置。 - 删除最大的元素
我们可以从数组的顶端删去最大的元素，并将数组的最后一个元素放到顶端，并让它下沉到合适的位置。
据此我们可以实现基于堆的优先队列：
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 v){
pq[++N] = v;
swim(N);
}
public Key delMax(){
Key max = pq[1];
exch(1,N--);
pq[N+1] = null;
sink(1);
return max;
}
private boolean less(int i, int j){
return pq[i].compareTo(pq[i]) < 0;
}
private void exch(int i, int j){
Key t = pq[i];
pq[i] = pq[j];
pq[j] = t;
}
}
针对基于堆的优先队列，我们有如下命题：
对于一个含有N个元素的基于堆的优先队列，插入元素的操作只需要不超过(lgN+1)次的比较，删除最大元素的操作需要不超过2lgN次比较。
