第C#實現優先隊列和堆排序目錄優先隊列1.API2.初級實現3.堆的定義二叉堆表示法4.堆的算法上浮（由下至上的堆的有序化）下沉（由上至下的堆的有序化）改進堆排序1.堆的構造2.下沉排序先下沉后上浮

優先隊列

許多應用程序都需要處理有序的元素，但不一定要求它們全部有序，或是不一定要一次就將它們排序。很多情況下是收集一些元素，處理當前鍵值最大的元素，然后再收集更多的元素，再處理當前鍵值最大的元素。這種情況下，需要的數據結構支持兩種操作：刪除最大的元素和插入元素。這種數據結構類型叫優先隊列。

這里，優先隊列基于二叉堆數據結構實現，用數組保存元素并按照一定條件排序，以實現對數級別的刪除和插入操作。

1.API

優先隊列是一種抽象數據類型，它表示了一組值和對這些值的操作，抽象層使應用和實現隔離開來。

2.初級實現

1.無序數組實現

優先隊列的insert方法和下壓棧的push方法一樣。刪除最大元素時，遍歷數組找出最大元素，和邊界元素交換。2.有序數組實現

插入元素時，將較大的元素向右移一格（和插入排序一樣）。這樣刪除時，就可以直接pop。

使用鏈接也是一樣的邏輯。

這些實現總有一種操作需要線性級別的時間復雜度。使用二叉堆可以保證操作在對數級別的時間完成。

3.堆的定義

數據結構二叉堆可以很好地實現優先隊列地基本操作。在二叉堆數組中，每個元素都要保證大于等于另兩個特定位置地元素。同樣，這兩個位置地元素又至少要大于等于數組中另外兩個元素，以此類推。用二叉樹表示：

當一棵二叉樹的每個結點都大于等于它的兩個子節點時，它被成為堆有序。從任意結點向上，都能得到一列非遞減的元素；從任意結點向下，都能得到一列非遞增的元素。根結點是堆有序的二叉樹中最大的結點。

二叉堆表示法

這里使用完全二叉樹表示：將二叉樹的結點按照層級順序（從上到下，從左往右）放入數組中，不使用數組的第一個位置（為了方便計算），根結點在位置1，它的子結點在位置2和3，子結點的子結點分別在位置4，5，6，7，一次類推。

在一個二叉堆中，位置k的結點的父節點位置在k/2，而它的兩個子結點在2k和2k+1。可以通過計算數組的索引而不是指針就可以在樹中上下移動。

一棵大小為N的完全二叉樹的高度為lgN。

4.堆的算法

用長度為N+1的私有數組pq[]表示一個大小為N的堆。

堆在進行插入或刪除操作時，會打破堆的狀態，需要遍歷堆并按照要求將堆的狀態恢復。這個過程稱為堆的有序化。

堆的有序化分為兩種情況：當某個結點的優先級上升（或在堆底加入一個新的元素）時，需要由下至上恢復堆的順序；當某個結點的優先級下降（例如將根節點替換為一個較小的元素），需要由上至下恢復堆的順序。

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

當某個結點比它的父結點更大時，交換它和它的父節點，這個結點交換到它父節點的位置。但有可能比它現在的父節點大，需要繼續上浮，直到遇到比它大的父節點。（這里不需要比較這個子結點和同級的另一個子結點，因為另一個子結點比它們的父結點小）

//上浮

privatevoidSwim(intn)

while(n1Less(n/2,n))

Exch(n/2,n);

n=n/2;

}

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

當某個結點k變得比它的兩個子結點（2k和2k+1）更小時，可以通過將它和它的兩個子結點較大者交換來恢復堆有序。交換后在子結點處可能繼續打破堆有序，需要繼續重復下沉，直到它的子結點都比它小或到達底部。

//下沉

privatevoidSink(intk)

while(2*k=N)

intj=2*k;

//取最大的子節點

if(jNLess(j,j+1))

j++;

//如果父節點不小子節點，退出循環

if(!Less(k,j))

break;

//否則交換，繼續下沉

Exch(j,k);

k=j;

}

知道了上浮和下沉的邏輯，就可以很好理解在二叉堆中插入和刪除元素的邏輯。

插入元素：將新元素加到數組末尾，增加堆的大小并讓這個新元素上浮到合適的位置。

刪除最大元素：從數組頂端（即pq[1]）刪除最大元素，并將數組最后一個元素放到頂端，減少數組大小并讓這個元素下沉到合適位置。

publicclassMaxPriorityQueue

privateIComparable[]pq;

publicintN;

publicMaxPriorityQueue(intmaxN)

pq=newIComparable[maxN+1];

publicboolIsEmpty()

returnN==0;

publicvoidInsert(IComparablevalue)

pq[++N]=value;

Swim(N);

publicIComparableDeleteMax()

IComparablemax=pq[1];

Exch(1,N--);

pq[N+1]=null;

Sink(1);

returnmax;

//下沉

privatevoidSink(intk)

while(2*k=N)

intj=2*k;

//取最大的子節點

if(jNLess(j,j+1))

j++;

//如果父節點不小子節點，退出循環

if(!Less(k,j))

break;

//否則交換，繼續下沉

Exch(j,k);

k=j;

//上浮

privatevoidSwim(intn)

while(n1Less(n/2,n))

Exch(n/2,n);

n=n/2;

privatevoidExch(inti,intj)

IComparabletemp=pq[i];

pq[i]=pq[j];

pq[j]=temp;

privateboolLess(inti,intj)

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

}

上述算法對優先隊列的實現能夠保證插入和刪除最大元素這兩個操作的用時和隊列的大小成對數關系。這里省略了動態調整數組大小的代碼，可以參考下壓棧。

對于一個含有N個元素的基于堆的優先隊列，插入元素操作只需要不超過（lgN+1）次比較，因為N可能不是2的冪。刪除最大元素的操作需要不超過2lgN次比較（兩個子結點的比較和父結點與較大子節點的比較）。

對于需要大量混雜插入和刪除最大元素的操作，優先隊列很適合。

改進

1.多叉堆

基于數組表示的完全三叉樹：對于數組1至N的N個元素，位置k的結點大于等于位于3k-1,3k,3k+1的結點，小于等于位于（k+1）/3的結點。2.調整數組大小

使用動態數組，可以構造一個無需關注隊列大小的優先隊列。可以參考下壓棧。3.索引優先隊列

在許多應用程序中，允許客戶端引用優先級隊列中已經存在的項目是有意義的。一種簡單的方法是將唯一的整數索引與每個項目相關聯。

堆排序

我們可以把任意優先隊列變成一種排序方法：先將所有元素插入一個查找最小元素的優先隊列，再重復調用刪除操作刪除最小元素來將它們按順序刪除。這種排序成為堆排序。

堆排序的第一步是堆的構造，第二步是下沉排序階段。

1.堆的構造

簡單的方法是利用前面優先隊列插入元素的方法，從左到右遍歷數組調用Swim方法（由上算法所需時間和NlogN成正比）。一個更聰明高效的方法是，從右（中間位置）到左調用Sink方法，只需遍歷一半數組，因為另一半是大小為1的堆。這種方法只需少于2N次比較和少于N次交換。（堆的構造過程中處理的堆都比較小。例如，要構造一個127個元素的數組，需要處理32個大小為3的堆，16個大小為7的堆，8個大小為15的堆，4個大小為31的堆，2個大小為63的堆和1個大小為127的堆，因此在最壞情況下，需要32*1+16*2+8*3+4*4+2*5+1*6=120次交換，以及兩倍的比較）。

2.下沉排序

堆排序的主要工作在第二階段。將堆中最大元素和堆底元素交換，并下沉至N--。相當于刪除最大元素并將堆底元素放至堆頂（優先隊列刪除操作），將刪除的最大元素放入空出的數組位置。

publicclassMaxPriorityQueueSort

publicstaticvoidSort(IComparable[]pq)

intn=pq.Length;

for(vark=n/2;kk--)

Sink(pq,k,n);

//上浮需要遍歷全部

//for(vark=n;kk--)

//Swim(pq,k);

while(n1)

Exch(pq,1,n--);

Sink(pq,1,n);

privatestaticvoidSwim(IComparable[]pq,intn)

while(n1Less(pq,n/2,n))

Exch(pq,n/2,n);

n=n/2;

//下沉

privatestaticvoidSink(IComparable[]pq,intk,intN)

while(2*k=N)

intj=2*k;

//取最大的子節點

if(jNLess(pq,j,j+1))

j++;

//如果父節點不小子節點，退出循環

if(!Less(pq,k,j))

break;

//否則交換，繼續下沉

Exch(pq,j,k);

k=j;

privatestaticvoidExch(IComparable[]pq,inti,intj)

IComparabletemp=pq[i-1];

pq[i-1]=pq[j-1];

pq[j-1]=temp;

privatestaticboolLess(IComparable[]pq,inti,intj)

returnpq[i-1].CompareTo(pq[j-1])

publicstaticvoidShow(IComparable[]a)

for(vari=0;ia.Length;i++)

Console.WriteLine(a[i]);

}

堆排序的軌跡

將N個元素排序，堆排序只需少于（2NlgN+2N）次比較以及一半次數的交換。2N來自堆的構造，2NlgN是每次下沉操作最多需要2lgN次比較。

先下沉后上浮

在排序過程中，大多數重新插入堆中的項目都會一直到達底部。因此，通過避免檢查元素是否已到達其位置，可以簡單地提升兩個子結點中的較大者直到到達底部，然后上浮到適當位置，從