為什么需要優(yōu)先隊(duì)列
我們并不一是一直都需要所有的元素全部有序棺克。很多情況下我們會(huì)選擇收集一些元素悠垛，然后處理其中鍵最大的元素，然后再收集更多的元素娜谊，再處理其中鍵值最大的元素确买。例如：你擁有一臺(tái)可以同時(shí)運(yùn)行多個(gè)程序的電腦，這是通過(guò)為每一個(gè)應(yīng)用程序的事件分配一個(gè)優(yōu)先級(jí)纱皆，并總是先處理優(yōu)先級(jí)最高的事件湾趾。例如手機(jī)來(lái)電事件和你正在玩的手機(jī)游戲事件，絕大多數(shù)手機(jī)都會(huì)給手機(jī)來(lái)電事件分配一個(gè)更高的優(yōu)先級(jí)派草，優(yōu)先處理搀缠，所以你的游戲被打斷，只能先處理來(lái)電近迁。
這種情況下艺普，需要支持以下兩種操作的數(shù)據(jù)結(jié)構(gòu)：
1.刪除最大元素。
2.插入元素。
這種數(shù)據(jù)結(jié)構(gòu)叫做優(yōu)先隊(duì)列歧譬。
API
優(yōu)先隊(duì)列是一種抽象的數(shù)據(jù)類(lèi)型岸浑，它表示了一組值和對(duì)這些值的操作，它的抽象層是我們能夠方便的將用例和實(shí)現(xiàn)隔離開(kāi)來(lái)瑰步。
public class MaxPQ<Key extends Comparable<Key>>
MaxPQ() 創(chuàng)建一個(gè)優(yōu)先隊(duì)列
MaxPQ(int max) 創(chuàng)建一個(gè)初始容量為max的優(yōu)先隊(duì)列
MaxPQ(Key[] a) 用a[]中的元素創(chuàng)建一個(gè)優(yōu)先隊(duì)列
void Insert(Key v) 向優(yōu)先隊(duì)列中插入一個(gè)元素
Key max() 返回最大元素
boolean isEmpty() 返回隊(duì)列是否為空
int size() 返回優(yōu)先隊(duì)列中元素的個(gè)數(shù)
這份API可以有很多種實(shí)現(xiàn)助琐，比如有序數(shù)組，無(wú)序數(shù)組面氓，鏈表，但它們?cè)谧顗牡那闆r下插入元素和刪除元素兩個(gè)操作需要線性時(shí)間來(lái)完成蛆橡，但是基于數(shù)據(jù)結(jié)構(gòu)"堆"的實(shí)現(xiàn)能夠保證這兩種操作都能更快的執(zhí)行：
堆的定義
堆有序：當(dāng)一棵二叉樹(shù)的每個(gè)節(jié)點(diǎn)都大于等于它的兩個(gè)字節(jié)點(diǎn)時(shí)，它被稱(chēng)為堆有序泰演。
完全二叉樹(shù)只用數(shù)組而不用指針就能表示。具體的方法是將二叉樹(shù)的節(jié)點(diǎn)按照層級(jí)順序放到數(shù)組中睦焕，根節(jié)點(diǎn)在位置一藐握，它的子節(jié)點(diǎn)在2和3，而子節(jié)點(diǎn)的子節(jié)點(diǎn)則在4垃喊，5猾普，6，7本谜，以此類(lèi)推初家。
二叉堆(簡(jiǎn)稱(chēng)堆)：二叉堆是一組能夠用堆有序的完全二叉樹(shù)排序的元素乌助，并在數(shù)組中按層級(jí)存儲(chǔ)溜在。
用堆實(shí)現(xiàn)的完全二叉樹(shù)的結(jié)構(gòu)是非常嚴(yán)格的，但它的靈活性已經(jīng)足以讓我們高效的實(shí)現(xiàn)優(yōu)先隊(duì)列他托。用它們我們將能夠?qū)崿F(xiàn)對(duì)數(shù)級(jí)別的插入元素和刪除最大元素的操作掖肋。
基于堆的優(yōu)先隊(duì)列的代碼實(shí)現(xiàn)
public class MaxPQ <Key extends Comparable<Key>>{
private Key[] pq; //堆有序的完全二叉樹(shù)
private int N = 0; //數(shù)據(jù)存儲(chǔ)在pq[1...N]中，pq[0]沒(méi)有使用
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]; //從根節(jié)點(diǎn)得到最大的元素
exchange(1,N--); //將其和最后一個(gè)節(jié)點(diǎn)交換
pq[N+1] = null; //防止對(duì)象游離
sink(1); //恢復(fù)堆的有序性
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()方法在插入元素的時(shí)候調(diào)用志笼，當(dāng)新元素加入的時(shí)候，需要比較它與父節(jié)點(diǎn)的大小登刺，如果新節(jié)點(diǎn)比父節(jié)點(diǎn)大籽腕，就要將其與父節(jié)點(diǎn)的元素交換，sink()方法在刪除最大元素的時(shí)候調(diào)用纸俭，當(dāng)刪除了最大元素的時(shí)候皇耗，就數(shù)組最后一個(gè)元素放到第一個(gè)位置，然后將其與字節(jié)點(diǎn)比較揍很，如果它比字節(jié)點(diǎn)小郎楼，就要將其下放万伤，直到它被放到了合適的位置。
由代碼實(shí)現(xiàn)我們很容易就可以得到對(duì)于一個(gè)含有N個(gè)元素的基于堆的優(yōu)先隊(duì)列呜袁，插入元素只需要不超過(guò)lgN+1次比較敌买，而刪除最大元素的操作需要不超過(guò)2lgN次比較。
堆排序
堆排序的思想：構(gòu)造一個(gè)堆阶界，然后依次從堆中拿出最大的元素虹钮，排序也就完成了。
實(shí)現(xiàn)代碼：
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;
}
}
}
在排序方法中膘融，先創(chuàng)建一個(gè)比原數(shù)組多一個(gè)元素的數(shù)組芙粱，然后將原數(shù)組復(fù)制到新數(shù)組的1～N位上，開(kāi)始構(gòu)造一個(gè)二叉堆氧映，構(gòu)造完二叉堆后春畔，每一次都將最大的元素（index為1）與后面的元素交換（1和N換，1和N－1換岛都，1和N-2換 etc.）在換的過(guò)程中不斷調(diào)用下沉方法保證堆有序律姨，這樣就能將數(shù)組從小到大排序，然后將元素復(fù)制回原數(shù)組臼疫，排序就完成了择份。
