前言

• 高級數(shù)據(jù)結(jié)構(gòu)（Ⅱ）優(yōu)先隊(duì)列（Priority Queue）
• API
• 堆的定義
• 二叉堆表示法
• 堆的算法
• 基于堆的優(yōu)先隊(duì)列
• 堆排序

高級數(shù)據(jù)結(jié)構(gòu)（Ⅱ）優(yōu)先隊(duì)列（Priority Queue）

許多應(yīng)用程序都需要處理有序的元素，但不一定要求它們?nèi)坑行?，或是不一定要一次就將它們排序。很多情況下我們會收集一些元素，處理當(dāng)前鍵值最大的元素，然后再收集更多的元素，再處理當(dāng)前鍵值最大的元素，如此這般。例如，你可能有一臺能夠同時(shí)運(yùn)行多個(gè)應(yīng)用程序的電腦（或者手機(jī)）。這是通過為每個(gè)應(yīng)用程序事件分配一個(gè)優(yōu)先級，并總是處理下一個(gè)優(yōu)先級最高的事件來實(shí)現(xiàn)的。例如，絕大多數(shù)手機(jī)分配給來電的優(yōu)先級都會被游戲程序的高。

在這種情況下，一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)應(yīng)該支持兩種操作：刪除最大元素和插入元素。這種數(shù)據(jù)類型叫做優(yōu)先隊(duì)列。優(yōu)先隊(duì)列的使用和隊(duì)列（刪除最老的元素）以及棧（刪除最新的元素）類似，但高效地實(shí)現(xiàn)它則更有挑戰(zhàn)性。

在本篇中，我們會學(xué)習(xí)一種基于二叉堆數(shù)據(jù)結(jié)構(gòu)的一種優(yōu)先隊(duì)列的經(jīng)典實(shí)現(xiàn)方法，用數(shù)組保存元素并按照一定條件排序，以實(shí)現(xiàn)高效地（對數(shù)級別的）刪除最大元素和插入元素操作。

API

優(yōu)先隊(duì)列是一種抽象數(shù)據(jù)類型，它表示了一組值和對這些值的操作，它的抽象層使我們能夠方便地將應(yīng)用程序和各種具體實(shí)現(xiàn)隔離開來。

實(shí)現(xiàn)

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() //返回最大元素
Key delMax() //刪除并返回最大元素
boolean isEmpty() //返回隊(duì)列是否為空
int size() //返回優(yōu)先隊(duì)列中元素個(gè)數(shù)

堆的定義

數(shù)據(jù)結(jié)構(gòu)二叉堆能夠很好地實(shí)現(xiàn)優(yōu)先隊(duì)列的基本操作。在二叉堆的數(shù)組中，每個(gè)元素都要保證大于等于另外兩個(gè)特定位置的元素。相應(yīng)地，這些位置的元素又至少要大于等于數(shù)組中的另外兩個(gè)元素，以此類推。如果我們將所有的元素畫成一顆二叉樹，將每個(gè)較大元素和較小的元素用邊連接就可以很容易地看出這種結(jié)構(gòu)。

命題：當(dāng)一顆二叉樹的每個(gè)結(jié)點(diǎn)都大于等于它的另外兩個(gè)子節(jié)點(diǎn)時(shí)，它被稱為堆有序。

相應(yīng)地，在堆有序的二叉樹中，每個(gè)結(jié)點(diǎn)都小于等于它的父節(jié)點(diǎn)（如果有的話）。從任意結(jié)點(diǎn)向上，我們都能得到一列非遞減的元素；從任意結(jié)點(diǎn)向下，我們都能得到一列非遞增的元素。

命題：根節(jié)點(diǎn)是堆有序的二叉樹中最大的結(jié)點(diǎn)

二叉堆表示法

如果我們用指針來表示堆有序的二叉樹，那么每個(gè)元素都需要三個(gè)指針來找到它的上下結(jié)點(diǎn)（父節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)）。如下圖所示，如果我們使用完全二叉樹，表達(dá)就會變的特別方便

可以先定下根節(jié)點(diǎn)，然后一層一層地由上向下、從左至右，在每個(gè)結(jié)點(diǎn)的下方連接兩個(gè)更小的結(jié)點(diǎn)，直至將N個(gè)結(jié)點(diǎn)全部連接完畢。完全二叉樹只用數(shù)組而不需要指針就可以表示。具體方法就是將二叉樹的結(jié)點(diǎn)按照層級順序放入數(shù)組中，根結(jié)點(diǎn)在位置1，它的子節(jié)點(diǎn)在位置2和位置3，而子節(jié)點(diǎn)的子節(jié)點(diǎn)分別在位置4、5、6和7，以此類推。

定義：二叉堆是一組能夠用堆有序的完全二叉樹排序的元素，并在數(shù)組中按照層級存儲（不使用數(shù)組的第一個(gè)位置）

在一個(gè)堆中，位置k的結(jié)點(diǎn)的父節(jié)點(diǎn)的位置為[k/2]向下取整，而它的兩個(gè)子節(jié)點(diǎn)的位置則分別為2k和2k+1。用數(shù)組（堆）實(shí)現(xiàn)的完全二叉樹的結(jié)構(gòu)是很嚴(yán)格的，但它的靈活性已經(jīng)足以讓我們高效地實(shí)現(xiàn)優(yōu)先隊(duì)列。用它們我們能將實(shí)現(xiàn)對數(shù)級別的插入元素和刪除最大元素的操作。利用數(shù)組中無需指針即可沿樹上下移動的便利和以下性質(zhì)，算法保證了對數(shù)復(fù)雜度的性能。

命題：一顆大小為N的完全二叉樹的高度為lg[N]

堆的算法

我們用長度為N+1的私有數(shù)組pq[]來表示一個(gè)大小為N的堆。我們不會使用pq[0]，堆元素放在pq[1]至pq[N]中。在排序算法中，我們只通過私有輔助函數(shù)less()和exch()來訪問元素，但因?yàn)樗械脑囟荚跀?shù)組pq[]中，我們在下面基于堆的優(yōu)先隊(duì)列中會用更緊湊的實(shí)現(xiàn)方式，不再將數(shù)組作為參數(shù)傳遞。堆的操作會首先進(jìn)行一些簡單的改動，打破堆的狀態(tài)，然后再遍歷堆并按照要求將堆的狀態(tài)恢復(fù)。我們稱這個(gè)過程為堆的有序化（reheapifying）。

實(shí)現(xiàn)：

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;
}

在堆有序化的過程中我們會遇到兩種情況。當(dāng)某個(gè)結(jié)點(diǎn)的優(yōu)先級上升（或是在堆底加入一個(gè)新的元素）時(shí)，我們需要由下至上恢復(fù)堆的順序。當(dāng)某個(gè)結(jié)點(diǎn)的優(yōu)先級下降（例如，將根節(jié)點(diǎn)替換為一個(gè)較小的元素）時(shí)，我們需要由下至上恢復(fù)堆的順序。首先來學(xué)習(xí)如何實(shí)現(xiàn)這兩種輔助操作，然后再用它們實(shí)現(xiàn)插入元素和刪除最大元素的操作。

由下至上的堆的有序化（上?。?/strong>

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++;
if(!less(k, j)) break;
exch(k, j);
k = j;
}
}

public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq; //基于堆的完全二叉樹
private int N = 0; //存儲于pa[1..N]中，pq[0]沒有使用
public MaxPQ(int maxN) {
pq = (Key[]) new Comparable[maxN + 1];
this.N = maxN;
}
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 v) {
Key max = pq[1]; //根節(jié)點(diǎn)得到最大元素
exch(1, N--); //將其和最后一個(gè)結(jié)點(diǎn)交換
pq[N + 1] = null; //防止對象游離
sink(1); //恢復(fù)堆的有序性
return max;
}
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;
}
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++;
if(!less(k, j)) break;
exch(k, j);
k = j;
}
}
}