第C++高級(jí)數(shù)據(jù)結(jié)構(gòu)之優(yōu)先隊(duì)列目錄前言高級(jí)數(shù)據(jù)結(jié)構(gòu)（Ⅱ）優(yōu)先隊(duì)列（PriorityQueue）API實(shí)現(xiàn)堆的定義二叉堆表示法堆的算法插入元素刪除最大元素基于堆的優(yōu)先隊(duì)列堆排序

前言

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

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

許多應(yīng)用程序都需要處理有序的元素，但不一定要求它們?nèi)坑行颍蚴遣灰欢ㄒ淮尉蛯⑺鼈兣判颉：芏嗲闆r下我們會(huì)收集一些元素，處理當(dāng)前鍵值最大的元素，然后再收集更多的元素，再處理當(dāng)前鍵值最大的元素，如此這般。例如，你可能有一臺(tái)能夠同時(shí)運(yùn)行多個(gè)應(yīng)用程序的電腦（或者手機(jī)）。這是通過(guò)為每個(gè)應(yīng)用程序事件分配一個(gè)優(yōu)先級(jí)，并總是處理下一個(gè)優(yōu)先級(jí)最高的事件來(lái)實(shí)現(xiàn)的。例如，絕大多數(shù)手機(jī)分配給來(lái)電的優(yōu)先級(jí)都會(huì)被游戲程序的高。

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

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

API

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

實(shí)現(xiàn)

publicclassMaxPQKeyextendsComparableKey

-----------------------------------------------------------------------

MaxPQ()//創(chuàng)建一個(gè)優(yōu)先隊(duì)列

MaxPQ(intmax)//創(chuàng)建一個(gè)初始容量為max的優(yōu)先隊(duì)列

MaxPQ(Key[]a)//用a中的元素創(chuàng)建一個(gè)優(yōu)先隊(duì)列

voidinsert(Keyv)//向優(yōu)先隊(duì)列中插入一個(gè)元素

Keymax()//返回最大元素

KeydelMax()//刪除并返回最大元素

booleanisEmpty()//返回隊(duì)列是否為空

intsize()//返回優(yōu)先隊(duì)列中元素個(gè)數(shù)

堆的定義

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

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

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

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

二叉堆表示法

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

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

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

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

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

堆的算法

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

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

privatebooleanless(inti,intj){

returnpq[i].compareTo(pq[j])

privatevoidexch(inti,intj){

Keyt=pq[i];

pq[i]=pq[j];

pq[j]=t;

}

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

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

如果堆的有序狀態(tài)因?yàn)槟硞€(gè)結(jié)點(diǎn)變得比它的父節(jié)點(diǎn)更大而被打破，那么我們就需要通過(guò)交換它和它的父節(jié)點(diǎn)來(lái)修復(fù)堆。交換后，這個(gè)結(jié)點(diǎn)比它的兩個(gè)子結(jié)點(diǎn)都大（一個(gè)是曾經(jīng)的父節(jié)點(diǎn)，另一個(gè)比它更小，因?yàn)樗撬?jīng)父節(jié)點(diǎn)的子節(jié)點(diǎn)），但這個(gè)結(jié)點(diǎn)仍然可能比它現(xiàn)在的父節(jié)點(diǎn)更大。我們可以一遍遍地用同樣的方法恢復(fù)秩序，將這個(gè)結(jié)點(diǎn)不斷向上移動(dòng)直到我們遇到了一個(gè)更大的父節(jié)點(diǎn)。位置k的結(jié)點(diǎn)的父結(jié)點(diǎn)為[k/2]，swim()方法中的循環(huán)可以保證只有位置k上的結(jié)點(diǎn)大于它的父節(jié)點(diǎn)時(shí)堆的有序狀態(tài)才會(huì)被打破。因此只要該結(jié)點(diǎn)不再大于父結(jié)點(diǎn)，堆的有序狀態(tài)就恢復(fù)了。當(dāng)一個(gè)結(jié)點(diǎn)優(yōu)先級(jí)太大的時(shí)候它需要?。╯wim）到堆的更高層，詳細(xì)代碼如下

privatevoidswim(intk){

while(k1less(k/2,k)){

exch(k/2,k);

k=k/2;

}

由上至下的堆的有序化（下沉）

如果堆的有序狀態(tài)因?yàn)槟硞€(gè)結(jié)點(diǎn)變得比它的兩個(gè)子結(jié)點(diǎn)或是其中之一更小了而被打破了，那么我們可以通過(guò)將它和它的兩個(gè)子結(jié)點(diǎn)中的較大者交換來(lái)恢復(fù)堆。交換可能會(huì)在子結(jié)點(diǎn)處繼續(xù)打破堆的有序狀態(tài)，因此我們都需要用相同的方式來(lái)將其修復(fù)，將結(jié)點(diǎn)向下移動(dòng)直到它的子結(jié)點(diǎn)都比它更小或者是達(dá)到了堆的底部。由位置為k的結(jié)點(diǎn)的子結(jié)點(diǎn)為2k和2k+1可以直接得到對(duì)應(yīng)的代碼。方法名為了形象表示這個(gè)過(guò)程稱為sink()下沉，即當(dāng)一個(gè)結(jié)點(diǎn)優(yōu)先級(jí)太低時(shí)它需要沉（sink）到堆的更低層，

碼實(shí)現(xiàn)如下：

privatevoidsink(intk){

while(2*k=N){

intj=2*k;

if(jNless(j,j+1))j++;

if(!less(k,j))break;

exch(k,j);

k=j;

}

插入元素

我們將新元素插入到數(shù)組末尾，增加堆的大小并讓這個(gè)元素上浮到合適的位置（如下圖左半部分所示）

刪除最大元素

我們從數(shù)組頂端刪去最大的元素并將數(shù)組的最后一個(gè)元素放到頂端，減小堆的大小并讓這個(gè)元素下沉到合適的位置（如下圖右半部分所示）

基于堆的優(yōu)先隊(duì)列

優(yōu)先隊(duì)列由一個(gè)基于堆的完全二叉樹(shù)表示，存儲(chǔ)于數(shù)組pq[1..N]中，pq[0]沒(méi)有使用，pq[0]的值有時(shí)可以作為哨兵來(lái)用。在insert()中，我們將N加1并把新元素添加在數(shù)組最后，然后用swim()恢復(fù)堆的秩序。在delMax()中，我們從pq[1]中得到需要返回的元素，然后將pq[N]移動(dòng)到pq[1]，將N減1并用sink()來(lái)恢復(fù)堆的秩序。同時(shí)我們還將不再使用的pq[N+1]設(shè)為null，以便系統(tǒng)回收它所占用的空間。此處省略動(dòng)態(tài)調(diào)整數(shù)組大小的代碼，有興趣的朋友可以自己寫(xiě)寫(xiě)。

命題：對(duì)于一個(gè)含有N個(gè)元素的基于堆的優(yōu)先隊(duì)列，插入元素操作只需不超過(guò)（lgN+1）次比較，刪除最大元素的操作需要不超過(guò)2lgN次比較

基于堆的優(yōu)先隊(duì)列詳細(xì)代碼如下：

publicclassMaxPQKeyextendsComparableKey{

privateKey[]pq;//基于堆的完全二叉樹(shù)

privateintN=0;//存儲(chǔ)于pa[1..N]中，pq[0]沒(méi)有使用

publicMaxPQ(intmaxN){

pq=(Key[])newComparable[maxN+1];

this.N=maxN;

publicbooleanisEmpty(){

returnN==0;

publicintsize(){

returnN;

publicvoidinsert(Keyv){

pq[++N]=v;

swim(N);

publicKeydelMax(Keyv){

Keymax=pq[1];//根節(jié)點(diǎn)得到最大元素

exch(1,N--);//將其和最后一個(gè)結(jié)點(diǎn)交換

pq[N+1]=null;//防止對(duì)象游離

sink(1);//恢復(fù)堆的有序性

returnmax;

privatebooleanless(inti,intj){

returnpq[i].compareTo(pq[j])

privatevoidexch(inti,intj){

Keyt=pq[i];

pq[i]=pq[j];

pq[j]=t;

privatevoidswim(intk){

while(k1less(k/2,k)){

exch(k/2,k);

k=k/2;

privatevoidsink(intk){

while(2*k=N){

intj=2*k;

if(jNless(j,j+1))j++;

if(!less(k,j))break;

exch(k,j);

k=j;

}

過(guò)程：

堆排序

堆排序可