使用二叉堆設計基于.NET的泛型優先級隊列

黃明志

（仲愷農業工程學院信息科學與技術學院，廣州 510225）

0 引言

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

1 基本算法

1.1 二叉堆

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

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

二叉堆具有的特性：一是根節點的優先級最高；二是當新增節點或移除根節點后能夠快速地重新建堆。因此，使用堆來存放元素是非常適合優先級隊列這種數據結構的。

1.2 計算子節點的索引

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

1.3 堆化

堆化是指將數組變為最小堆（或最大堆）數組的操作。對于存儲有n個節點的堆數組，堆化操作依次地從n/2-1開始，直到編號為0的節點。如果要將整個堆堆化為最小堆，則每次操作就是要比較當前節點與其子節點的值，確保當前節點的值比子節點的要小；否則，就將當前節點與其子節點進行交換，使其滿足最小堆的性質。例如，假設數組共有9個元素，初始時處于無序狀態（如圖1）；堆化操作將從索引為3（計算方法為：9/2-1，取整后為3）的節點開始，通過比較，發現其右子節點的值較小，故需對調其位置（如圖2）；同理，當堆化索引為1的節點時，首先是值為1和4的兩個節點的位置對調（箭頭1，如圖3），然后是值為4和3的兩個節點的位置也對調（箭頭2）；整棵二叉樹完全堆化后如圖4所示。

圖1 初始時的無序狀態

圖2 堆化索引為3的節點

圖3 堆化索引為1的節點

圖4 堆化完成后的狀態

2 具體設計

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

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

圖5 PriorityQueue和Enumerator類的UML圖

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

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

modified標志供迭代時若發現隊列中有任何元素被更改時作適當的處理。

2.1 構造函數

PriorityQueue共有七個重載的構造函數，其中的六個構造函數實際上通過this關鍵字調用如下的構造函數間接地實現，以盡可能地重用代碼：

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

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

2.2 入隊

元素入隊時，若發現數組已滿，則將數組的容量擴大一倍的操作由Array.Resize實施。

其中，SiftUp方法是將入隊元素調整到恰當的位置，以確保整個堆仍然處于最小堆的狀態。

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

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

2.3 出隊

由于堆處于最小堆狀態，因此，出隊的操作就是返回數組中的第一個元素。當然，返回并移除優先級最高的元素時，需要進行必要的調整，以確保堆再次處于最小堆的狀態。另外，當隊列為空（無元素）時拋出InvalidOperationException異常（這與.NET中Queue類中的相應出隊操作相同）：

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

顯而易見，Peek操作無需調用SiftDown方法，其時間復雜度為 O（1）。

2.4 實現枚舉數與簡單迭代

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

（1）MoveNext方法

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

（2）Current屬性

通過Current屬性，獲取集合中的當前元素。public E Current

（3）獲取枚舉數并實現IEnumerable泛型接口設計好Enumerator泛型類后，在優先級隊列中獲取枚舉數以實現IEnumerable接口的方法如下：

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

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

2.5 實現ICollection及相關接口

（1）實現接口中的基本成員

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

（2）實現顯式接口

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

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

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

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

3 測試

3.1 以實現IComparerable的類作為元素的測試

對于實現IComparerable并使用實現此接口的CompareTo方法作為元素的優先級比較方法的情形，在構造優先級隊列時，可省略IComparer參數以使用默認比較器。

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

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

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

當元素類并沒有實現IComparerable接口或優先級不使用此內置接口直接進行比較時，需自定義一個比較器類，然后在構造優先級隊列時，將此比較器的實例作為實參傳入。測試代碼先定義一個線程優先級比較器，然后使用此比較器實現將優先級別高的線程優先出隊。

4 結語

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