WEB开发网
开发学院软件开发C语言 用 C# 实现优先队列 阅读

用 C# 实现优先队列

 2009-04-20 08:26:21 来源:WEB开发网   
核心提示:优先队列(priority queue) 是很重要的数据结构,我在做 ACM 题时就经常要用到她,用 C# 实现优先队列,C++ STL 就包括 priority_queue ,Java 也有 PriorityQueue 类,程序代码只有 23 行,但是效率不高,遗憾的是,.NET Framework Base Cla

优先队列(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)。

Tags:实现 优先 队列

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接