PriorityQueue是一种抽象数据类型，它表示了一组值和对这些值的操作，支持两种操作：删除最大元素和插入元素。它的适用场景可能是金融事务，你需要从中找出最大的那些；或是农产品中的杀虫剂含量，这时你需要从
中找出最小的那些， 等等
java 版的 MaxPQ 模板
public class MaxPQ <Key extends Comparable<Key>> {
MaxPQ(Key[] a) 用 a[] 中的元素创建一个优先队列
void insert(Key v) 向优先队列中插入一个元素
Key max() 返回最大元素
Key delMax() 删除并返回最大元素
boolean isEmpty() 返回队列是否为空
int size() 返回优先队列中的元素个数
}
使用二叉堆实现优先队列
二叉堆定义
二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存（不使
用数组的第一个位置）
在一个堆中，位置 k 的结点的父结点的位置为k/2，而它的两个子结点的位置则分别为 2k 和 2k+1。在排序算法中，我们只通过私有辅助函数 less() 和 exch() 来访问元素
用它们我们将能实现对数级别的插入元素和删除最大元素的操作。利用在数组中无需指针即可沿树上下移动的便利和以下性质，算法保证了对数复杂度的性能。
堆的算法
我们用长度为 N+1 的私有数组 pq[] 来表示一个大小为 N 的堆，我们不会使 用 pq[0]， 堆 元 素 放 在 pq[1] 至pq[N] 中。
由下至上的堆有序化（上浮 swim）
由上至下的堆有序化（下沉 sink）
堆的操作
插入元素: 我们将新元素加到数组末尾，增加堆的大小并让这个新元素上浮到合适的位置
删除最大元素: 我们从数组顶端删去最大的元素并将数组的最后一个元素放到顶端，减小堆的大小并让这个元素下沉到合适的位置
实现
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq; // 基于堆的完全二叉树
private int N = 0; // 存储于pq[1..N]中，pq[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 void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k/2, k);
k = k/2; // java 中向下取整
}
}
private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
private boolean less(int i, int j) {
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i, int j) {
Key t = pq[i];
pq[i] = pq[j];
pq[j] = t;
}
}
堆排序
public static void sort(Comparable[] a) {
int N = a.length;
for (int k = N/2; k >= 1; k--) { // for 循环构造了堆
sink(a, k, N);
}
while (N > 1) { // while 循环将最大的元素 a[1] 和 a[N] 交换并修复了堆，如此重复直到堆变空。
exch(a, 1, N--);
sink(a, 1, N);
}
}
小结
堆排序在排序复杂性的研究中有着重要的地位，因为它是我们所知的唯一能够同时最优地利用空间和时间的方法——在最坏的情况下它也能保证使用～ 2NlgN 次比较和恒定的额外空间。
当空间十分紧张的时候（例如在嵌入式系统或低成本的移动设备中）它很流行，因为它只用几行就能实现（甚至机器码也是）较好的性能。但现代系统的许多应用很少使用它，因为它无法利用缓存。数组元素很少和相邻的其他元素进行比较，因此缓存未命中的次数要远远高于大多数比较都在相邻元素间进行的算法，如快速排序、归并排序，甚至是希尔排序。
