用 C# 实现优先队列
2009-04-20 08:26:21 来源:WEB开发网优先队列(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)。