使用二叉堆設(shè)計基于.NET的泛型優(yōu)先級隊列

黃明志

（仲愷農(nóng)業(yè)工程學(xué)院信息科學(xué)與技術(shù)學(xué)院，廣州 510225）

0 引言

優(yōu)先級隊列類（PriorityQueue）是不同于一般的先進(jìn)先出隊列（如Queue類）的一種數(shù)據(jù)結(jié)構(gòu)。優(yōu)先級隊列中的各個元素具有可比較的優(yōu)先級，元素入隊的操作與先進(jìn)先出隊列相同，但出隊時，總是優(yōu)先級別最高的元素。元素的比較方法既可使用元素類型的默認(rèn)比較器進(jìn)行，也可依據(jù)構(gòu)造優(yōu)先級隊列實例時指定的類型比較器進(jìn)行。優(yōu)先級隊列廣泛應(yīng)用于寬帶管理、離散事件仿真、最佳優(yōu)先搜索算法和霍夫曼編碼等場景中。在C++和Java的類庫中，均有相應(yīng)的優(yōu)先級隊列，但遺憾的是，在.NET Framework中卻沒有相應(yīng)的公開類可以供開發(fā)者直接地使用。Web上雖然有一些用C#設(shè)計的優(yōu)先級隊列[1]，但其設(shè)計比較簡陋，離.NET Framework中System.Collections.Generic命名空間中的集合類相去甚遠(yuǎn)。因此，按.NET中已有泛型集合類的接口標(biāo)準(zhǔn)設(shè)計一個優(yōu)先級隊列十分必要。優(yōu)先級隊列的內(nèi)部使用一個表示二叉堆的數(shù)組來存放元素，充分利用堆的特性，可使入隊和出隊等基本操作的性能得到優(yōu)化。

1 基本算法

1.1 二叉堆

二叉堆是一棵完全二叉樹（Complete Binary Tree），對于每個父節(jié)點，它的值均小于等于（或大于等于）其子節(jié)點。而對于具有n個節(jié)點的完全二叉樹，可以按照從上到下（從根節(jié)點到葉節(jié)點）、從左到右的規(guī)則將各個節(jié)點映射到一個大小為n的一維數(shù)組中。

最小堆是指父節(jié)點的值均小于或等于其子節(jié)點的堆。而最大堆則是指父節(jié)點的值均大于或等于其子節(jié)點的堆。

二叉堆具有的特性：一是根節(jié)點的優(yōu)先級最高；二是當(dāng)新增節(jié)點或移除根節(jié)點后能夠快速地重新建堆。因此，使用堆來存放元素是非常適合優(yōu)先級隊列這種數(shù)據(jù)結(jié)構(gòu)的。

1.2 計算子節(jié)點的索引

計算某個節(jié)點的子節(jié)點在數(shù)組中基于0的索引的方法如下：對于某個索引為i的節(jié)點，左子節(jié)點的索引為2*i+1；而右子節(jié)點的索引則為2*（i+1），當(dāng)然，也可以表示為左節(jié)點的索引加1。

1.3 堆化

堆化是指將數(shù)組變?yōu)樽钚《眩ɑ蜃畲蠖眩?shù)組的操作。對于存儲有n個節(jié)點的堆數(shù)組，堆化操作依次地從n/2-1開始，直到編號為0的節(jié)點。如果要將整個堆堆化為最小堆，則每次操作就是要比較當(dāng)前節(jié)點與其子節(jié)點的值，確保當(dāng)前節(jié)點的值比子節(jié)點的要小；否則，就將當(dāng)前節(jié)點與其子節(jié)點進(jìn)行交換，使其滿足最小堆的性質(zhì)。例如，假設(shè)數(shù)組共有9個元素，初始時處于無序狀態(tài)（如圖1）；堆化操作將從索引為3（計算方法為：9/2-1，取整后為3）的節(jié)點開始，通過比較，發(fā)現(xiàn)其右子節(jié)點的值較小，故需對調(diào)其位置（如圖2）；同理，當(dāng)堆化索引為1的節(jié)點時，首先是值為1和4的兩個節(jié)點的位置對調(diào)（箭頭1，如圖3），然后是值為4和3的兩個節(jié)點的位置也對調(diào)（箭頭2）；整棵二叉樹完全堆化后如圖4所示。

圖1 初始時的無序狀態(tài)

圖2 堆化索引為3的節(jié)點

圖3 堆化索引為1的節(jié)點

圖4 堆化完成后的狀態(tài)

2 具體設(shè)計

PriorityQueue繼承于 IEnumerable、ICollection和IEnumerable三個接口，如圖5所示。其中，ICollection定義所有非泛型集合的大小、枚舉數(shù)和同步方法，而IEnumerable和IEnumerable則分別定義了泛型和非泛型的公開枚舉數(shù)，該枚舉數(shù)支持在集合上進(jìn)行簡單的迭代操作。

類的開始處的程序代碼如下：

圖5 PriorityQueue和Enumerator類的UML圖

基于性能的考慮，在PriorityQueue類的內(nèi)部，如上所述，使用了表示堆的數(shù)組heap來存儲隊列中的各個元素，數(shù)組的容量大小會隨著隊列元素的添加而自動增大，這種設(shè)計與.NET中Collections命名空間中相關(guān)的集合類的設(shè)計一致。

Comparer用于確定元素的優(yōu)先級的大小。其值可通過構(gòu)造函數(shù)傳遞過來，如果從構(gòu)造函數(shù)中傳遞過來的比較器為null，則使用相應(yīng)類型比較器的默認(rèn)值（即Comparer.Default）。對于以不繼承于IComparable接口的對象（如Thread對象）作為元素的優(yōu)先級隊列，在構(gòu)造函數(shù)中指定比較器是必須的。

modified標(biāo)志供迭代時若發(fā)現(xiàn)隊列中有任何元素被更改時作適當(dāng)?shù)奶幚怼?/p>

2.1 構(gòu)造函數(shù)

PriorityQueue共有七個重載的構(gòu)造函數(shù)，其中的六個構(gòu)造函數(shù)實際上通過this關(guān)鍵字調(diào)用如下的構(gòu)造函數(shù)間接地實現(xiàn)，以盡可能地重用代碼：

在實例化對象時，如果collection參數(shù)為非null，則需要進(jìn)行堆化操作。下述的Heapify方法建立最小堆：

對于最小堆來說，就像上述基本算法所介紹的那樣，SiftDown的作用是將一個節(jié)點和它的子節(jié)點進(jìn)行比較，保證它比其所有的子節(jié)點都要小，否則，就通過交換兩個節(jié)點來滿足這個要求。這個調(diào)整或交換的順序是從當(dāng)前節(jié)點向下，一直到葉節(jié)點為止：

2.2 入隊

元素入隊時，若發(fā)現(xiàn)數(shù)組已滿，則將數(shù)組的容量擴(kuò)大一倍的操作由Array.Resize實施。

其中，SiftUp方法是將入隊元素調(diào)整到恰當(dāng)?shù)奈恢茫源_保整個堆仍然處于最小堆的狀態(tài)。

入隊的元素可以為null，這樣的設(shè)計考慮使得PriorityQueue的行為與表現(xiàn)與.NET中的現(xiàn)有的Queue類相一致。

如果不考慮自動擴(kuò)展數(shù)組容量的操作，入隊操作的時間復(fù)雜度主要由SiftUp方法來決定，即其時間復(fù)雜度為 O（logN）。

2.3 出隊

由于堆處于最小堆狀態(tài)，因此，出隊的操作就是返回數(shù)組中的第一個元素。當(dāng)然，返回并移除優(yōu)先級最高的元素時，需要進(jìn)行必要的調(diào)整，以確保堆再次處于最小堆的狀態(tài)。另外，當(dāng)隊列為空（無元素）時拋出InvalidOperationException異常（這與.NET中Queue類中的相應(yīng)出隊操作相同）：

出隊操作的時間復(fù)雜度主要由SiftDown方法來決定，出隊操作的時間復(fù)雜度O（logN）。

顯而易見，Peek操作無需調(diào)用SiftDown方法，其時間復(fù)雜度為 O（1）。

2.4 實現(xiàn)枚舉數(shù)與簡單迭代

為了實現(xiàn)在泛型的優(yōu)先級隊列中進(jìn)行簡單迭代操作，同時讓優(yōu)先級隊列類的設(shè)計具有良好的封裝性，在PriorityQueue的內(nèi)部，設(shè)計了一個Enumerator私有類。在Enumerator的構(gòu)造函數(shù)中，將Priority-Queue的實例作為參數(shù)傳遞到其中。由于從本質(zhì)上而言，迭代操作不是線程安全的，如果在迭代操作正在進(jìn)行的時候，隊列中的任何元素出現(xiàn)了變化、隊列中添加或刪除了元素，均應(yīng)該拋出InvalidOperationException異常。

（1）MoveNext方法

Enumerator類定義了初始值為-1的整型數(shù)據(jù)成員position，用于指示當(dāng)前元素所在的位置。若MoveNext能正確地將“指針”指向下一個元素，則返回真；否則，返回假。

（2）Current屬性

通過Current屬性，獲取集合中的當(dāng)前元素。public E Current

（3）獲取枚舉數(shù)并實現(xiàn)IEnumerable泛型接口設(shè)計好Enumerator泛型類后，在優(yōu)先級隊列中獲取枚舉數(shù)以實現(xiàn)IEnumerable接口的方法如下：

通過上述的設(shè)計，就令PriorityQueue類支持C#中的foreach（或Visual Basic中的For Each）語義而循環(huán)地訪問集合中的各個元素了。但是，應(yīng)該注意，由于最小堆或最大堆的特性，這樣的迭代操作不能確保各元素是按優(yōu)先級順序出現(xiàn)的。如果要按優(yōu)先級進(jìn)行迭代操作，可以使用CopyTo方法將所有元素復(fù)制到另一個數(shù)組，然后再使用Array.Sort方法進(jìn)行排序。

實現(xiàn)IEnumerable泛型接口后，優(yōu)先級隊列類就自動地具有了System.Linq命名空間中所提供支持的語言集成查詢（LINQ）的功能了，即可以直接地使用其中的查詢類和接口中的Average、Max和Min等各種擴(kuò)展方法了。

2.5 實現(xiàn)ICollection及相關(guān)接口

（1）實現(xiàn)接口中的基本成員

ICollection接口主要有CopyTo和GetEnumerator方法以及Count、IsSynchronized和SyncRoot屬性。例如，獲取可用于同步ICollection訪問的對象的代碼為“public Object SyncRoot{get{return heap;}}”；而 IsSynchronized屬性總是返回false。

（2）實現(xiàn)顯式接口

優(yōu)先級隊列類實現(xiàn)了若干個顯式接口。例如，獲取一個循環(huán)訪問集合的枚舉數(shù)就有IEnumerable.GetE-numerator和IEnumerable.GetEnumerator兩個顯式接口方法。后者的實現(xiàn)如下：

而顯式接口ICollection.CopyTo的實現(xiàn)則如下：void ICollection.CopyTo（Array array，int arrayIndex）

而公共的CopyTo是通過顯式將this對象轉(zhuǎn)換為ICollection接口后調(diào)用上述顯式方法實現(xiàn)的，也就是說，其方法體中僅需“（（ICollection）this）.CopyTo（array，arrarIndex）”這樣一行語句即可。

為了更簡單起見，上述代碼中實例化各個異常時所傳入的用于描述異常信息的字符串僅以參數(shù)名表示，而實際上應(yīng)為可更明確地描述異常的文本。

3 測試

3.1 以實現(xiàn)IComparerable的類作為元素的測試

對于實現(xiàn)IComparerable并使用實現(xiàn)此接口的CompareTo方法作為元素的優(yōu)先級比較方法的情形，在構(gòu)造優(yōu)先級隊列時，可省略IComparer參數(shù)以使用默認(rèn)比較器。

如果要按從大到小的順序出隊，就需要設(shè)計一個比較器，將比較操作反轉(zhuǎn)。下面設(shè)計一個將優(yōu)先級反轉(zhuǎn)的類，以簡化這類常見操作的使用：

這樣，在構(gòu)造上述整型優(yōu)先級隊列時，使用以下的比較器實例作為實參來構(gòu)造隊列即可實現(xiàn)將出隊順序由使用默認(rèn)比較器時的從小到大反轉(zhuǎn)為從大到小了：Comparercomparer=new OppositeComparer（Comparer.Default）;

3.2 以沒有或非直接使用內(nèi)置IComparerable接口的類作為元素的測試

當(dāng)元素類并沒有實現(xiàn)IComparerable接口或優(yōu)先級不使用此內(nèi)置接口直接進(jìn)行比較時，需自定義一個比較器類，然后在構(gòu)造優(yōu)先級隊列時，將此比較器的實例作為實參傳入。測試代碼先定義一個線程優(yōu)先級比較器，然后使用此比較器實現(xiàn)將優(yōu)先級別高的線程優(yōu)先出隊。

4 結(jié)語

優(yōu)先級隊列在寬帶管理等應(yīng)用場景中被廣泛使用，而.NET中并沒有相應(yīng)的類。因PriorityQueue的設(shè)計與.NET Framework 3.5中System.Collections.Generic命名空間中相關(guān)泛型集合類的接口設(shè)計、命名規(guī)則、風(fēng)格、外觀、行為和使用方法相一致，具有良好的易用性和柔韌性，故此對此類的使用能無縫地溶入到System.Collections.Generic命名空間的集合類當(dāng)中——接口和使用方法完全與Queue類一樣，除了每次出隊操作總是優(yōu)先級最高的元素之外。同時，因優(yōu)先級隊列的內(nèi)部設(shè)計使用了算法高效的最小堆，故其在元素的存儲以及入隊、出隊等基本操作方面的時間和空間開銷少，可直接地滿足實際應(yīng)用場景的要求。