简述用C#实现优先队列方法

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

usingSystem;

usingSystemCollectionsGeneric;

namespaceSkyivUtil

{

classPriorityQueue<T>

{

IComparer<T>comparer;

T[]heap;

publicintCount{get;privateset;}

publicPriorityQueue():this(null){}

publicPriorityQueue(intcapacity):this(capacitynull){}

publicPriorityQueue(IComparer<T>comparer):this(comparer){}

publicPriorityQueue(intcapacityIComparer<T>comparer)

{

thiscomparer=(comparer==null)?Comparer<T>Default:comparer;

thisheap=newT[capacity];

}

publicvoidPush(Tv)

{

if(Count>=heapLength)ArrayResize(refheapCount*);

heap[Count]=v;

SiftUp(Count++);

}

publicTPop()

{

varv=Top();

heap[]=heap[Count];

if(Count>)SiftDown();

returnv;

}

publicTTop()

{

if(Count>)returnheap[];

thrownewInvalidOperationException(优先队列为空);

}

voidSiftUp(intn)

{

varv=heap[n];

for(varn=n/;n>&&comparerCompare(vheap[n])>;n=nn/=)heap[n]=heap[n];

heap[n]=v;

}

voidSiftDown(intn)

{

varv=heap[n];

for(varn=n*;n<Count;n=nn*=)

{

if(n+<Count&&comparerCompare(heap[n+]heap[n])>)n++;

if(comparerCompare(vheap[n])>=)break;

heap[n]=heap[n];

}

heap[n]=v;

}

}

}

如上所示这个

PriorityQueue<T>

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

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

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