使用二叉堆设计基于.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类一样，除了每次出队操作总是优先级最高的元素之外。同时，因优先级队列的内部设计使用了算法高效的最小堆，故其在元素的存储以及入队、出队等基本操作方面的时间和空间开销少，可直接地满足实际应用场景的要求。