为什么需要优先队列
我们并不一是一直都需要所有的元素全部有序。很多情况下我们会选择收集一些元素，然后处理其中键最大的元素，然后再收集更多的元素，再处理其中键值最大的元素。例如：你拥有一台可以同时运行多个程序的电脑，这是通过为每一个应用程序的事件分配一个优先级，并总是先处理优先级最高的事件。例如手机来电事件和你正在玩的手机游戏事件，绝大多数手机都会给手机来电事件分配一个更高的优先级，优先处理，所以你的游戏被打断，只能先处理来电。
这种情况下，需要支持以下两种操作的数据结构：
1.删除最大元素。
2.插入元素。
这种数据结构叫做优先队列。
API
优先队列是一种抽象的数据类型，它表示了一组值和对这些值的操作，它的抽象层是我们能够方便的将用例和实现隔离开来。
public class MaxPQ<Key extends Comparable<Key>>
MaxPQ() 创建一个优先队列
MaxPQ(int max) 创建一个初始容量为max的优先队列
MaxPQ(Key[] a) 用a[]中的元素创建一个优先队列
void Insert(Key v) 向优先队列中插入一个元素
Key max() 返回最大元素
boolean isEmpty() 返回队列是否为空
int size() 返回优先队列中元素的个数
这份API可以有很多种实现，比如有序数组，无序数组，链表，但它们在最坏的情况下插入元素和删除元素两个操作需要线性时间来完成，但是基于数据结构"堆"的实现能够保证这两种操作都能更快的执行：
来自《Algorithms Fourth Edition》一书的截图，侵删
堆的定义
堆有序：当一棵二叉树的每个节点都大于等于它的两个字节点时，它被称为堆有序。
来自《Algorithms Fourth Edition》一书的截图，侵删
完全二叉树只用数组而不用指针就能表示。具体的方法是将二叉树的节点按照层级顺序放到数组中，根节点在位置一，它的子节点在2和3，而子节点的子节点则在4，5，6，7，以此类推。
来自《Algorithms Fourth Edition》一书的截图，侵删
二叉堆(简称堆)：二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按层级存储。
用堆实现的完全二叉树的结构是非常严格的，但它的灵活性已经足以让我们高效的实现优先队列。用它们我们将能够实现对数级别的插入元素和删除最大元素的操作。
基于堆的优先队列的代码实现
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]; //从根节点得到最大的元素
exchange(1,N--); //将其和最后一个节点交换
pq[N+1] = null; //防止对象游离
sink(1); //恢复堆的有序性
return max;
}
private boolean less(int i, int j){
return pq[i].compareTo(pq[j]) < 0;
}
private void exchange(int i, int j){
Key t = pq[i];
pq[i] = pq[j];
pq[j] = t;
}
private void swim(int k){
while (k>1 && less(k/2, k)){
exchange(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++;
if (!less(k,j)) break;
exchange(k,j);
k = j;
}
}
}
其中较为重要的是swim()和sink()方法，swim()方法在插入元素的时候调用，当新元素加入的时候，需要比较它与父节点的大小，如果新节点比父节点大，就要将其与父节点的元素交换，sink()方法在删除最大元素的时候调用，当删除了最大元素的时候，就数组最后一个元素放到第一个位置，然后将其与字节点比较，如果它比字节点小，就要将其下放，直到它被放到了合适的位置。
由代码实现我们很容易就可以得到对于一个含有N个元素的基于堆的优先队列，插入元素只需要不超过lgN+1次比较，而删除最大元素的操作需要不超过2lgN次比较。
堆排序
堆排序的思想：构造一个堆，然后依次从堆中拿出最大的元素，排序也就完成了。
实现代码：
public class Heap {
private static Comparable[] a;
public static void sort(Comparable[] array){
a = new Comparable[array.length+1];
for (int i = 0; i < array.length; i++) a[i+1] = array[i];
int N = array.length;
for (int k = N/2; k >= 1; k--){
sink(k,N);
}
while (N>1){
exchange(1, N--);
sink(1,N);
}
for (int i = 0; i < array.length; i++) array[i] = a[i+1];
}
public static void main(String[] args){
Integer[] a = {0,9,8,7,6,5,6,5,6,98,7,6,5,3};
sort(a);
for (int i = 0; i < a.length;i++){
System.out.println(a[i]);
}
}
private static boolean less(int i, int j){
return a[i].compareTo(a[j]) < 0;
}
private static void exchange(int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void swim(int k){
while (k>1 && less(k/2, k)){
exchange(k/2,k);
k = k/2;
}
}
private static void sink(int k, int N){
while (2*k <= N){
int j = 2*k;
if (j<N && less(j,j+1)) j++;
if (!less(k,j)) break;
exchange(k,j);
k = j;
}
}
}
在排序方法中，先创建一个比原数组多一个元素的数组，然后将原数组复制到新数组的1～N位上，开始构造一个二叉堆，构造完二叉堆后，每一次都将最大的元素（index为1）与后面的元素交换（1和N换，1和N－1换，1和N-2换 etc.）在换的过程中不断调用下沉方法保证堆有序，这样就能将数组从小到大排序，然后将元素复制回原数组，排序就完成了。
网友评论