用 C# 实现优先队列

优先队列(priority queue) 是很重要的数据结构。我在做 ACM 题时就经常要用到她。C++ STL 就包括 priority_queue 。Java 也有 PriorityQueue 类。遗憾的是，.NET Framework Base Class Library 中并不包括优先队列。于是，我只好自己用 C# 语言写一个，如下所示：

using　System;
using　System.Collections.Generic;

namespace　Skyiv.Util
{
　class　PriorityQueue<T>
　{
　　IComparer<T>　comparer;
　　T[]　heap;

　　public　int　Count　{　get;　private　set;　}

　　public　PriorityQueue()　:　this(null)　{　}
　　public　PriorityQueue(int　capacity)　:　this(capacity,　null)　{　}
　　public　PriorityQueue(IComparer<T>　comparer)　:　this(16,　comparer)　{　}

　　public　PriorityQueue(int　capacity,　IComparer<T>　comparer)
　　{
　　　this.comparer　=　(comparer　==　null)　?　Comparer<T>.Default　:　comparer;
　　　this.heap　=　new　T[capacity];
　　}

　　public　void　Push(T　v)
　　{
　　　if　(Count　>=　heap.Length)　Array.Resize(ref　heap,　Count　*　2);
　　　heap[Count]　=　v;
　　　SiftUp(Count++);
　　}

　　public　T　Pop()
　　{
　　　var　v　=　Top();
　　　heap[0]　=　heap[--Count];
　　　if　(Count　>　0)　SiftDown(0);
　　　return　v;
　　}

　　public　T　Top()
　　{
　　　if　(Count　>　0)　return　heap[0];
　　　throw　new　InvalidOperationException("优先队列为空");
　　}

　　void　SiftUp(int　n)
　　{
　　　var　v　=　heap[n];
　　　for　(var　n2　=　n　/　2;　n　>　0　&&　comparer.Compare(v,　heap[n2])　>　0;　n　=　n2,　n2　/=　2)　heap[n]　=　heap[n2];
　　　heap[n]　=　v;
　　}

　　void　SiftDown(int　n)
　　{
　　　var　v　=　heap[n];
　　　for　(var　n2　=　n　*　2;　n2　<　Count;　n　=　n2,　n2　*=　2)
　　　{
　　　　if　(n2　+　1　<　Count　&&　comparer.Compare(heap[n2　+　1],　heap[n2])　>　0)　n2++;
　　　　if　(comparer.Compare(v,　heap[n2])　>=　0)　break;
　　　　heap[n]　=　heap[n2];
　　　}
　　　heap[n]　=　v;
　　}
　}
}

如上所示，这个 PriorityQueue<T>

泛型类提供四个公共构造函数，第一个是无参的构造函数，其余的构造函数允许指定优先队列中包括的初始元素数(capacity)、如何对键进行比较(comparer)。

这个程序使用堆(heap)来实现优先队列。所以，所需的空间是最小的。Count 属性和 Top 方法的时间复杂度是 O(1)，Push 和 Pop 方法的时间复杂度都是 O(logN)。

我曾经用 List<T> 泛型类实现过一个优先队列，请参见我的博客 Timus1016. A Cube on the Walk 。虽然更简单，程序代码只有 23 行，但是效率不高，其 Push 和 Pop 方法的时间复杂度都是 O(N)。