黃明志

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

0 引言

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

1 基本算法

1.1 二叉堆

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

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

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

1.2 計(jì)算子節(jié)點(diǎn)的索引

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

1.3 堆化

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

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

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

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

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

2 具體設(shè)計(jì)

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

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

圖5 PriorityQueue和Enumerator類的UML圖

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

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

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

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

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

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

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

2.2 入隊(duì)

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

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

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

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

2.3 出隊(duì)

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

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

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

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

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

（1）MoveNext方法

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

（2）Current屬性

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

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

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

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

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

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

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

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

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

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

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

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

3 測(cè)試

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

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

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

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

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

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

4 結(jié)語

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