c#实现优先级队列

http://www.baidu.com/s?wd=c%23%E4%BC%98%E5%85%88%E7%BA%A7%E9%98%9F%E5%88%97&ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=baidu&rsv_pq=efc07de5000f3769&rsv_t=cfc2XQdw6vLpqMbC%2BUKjZKG3pLY5QhlmymVHc2VGh8avPmrRmgHn5bRXbco&bs=%E4%BC%98%E5%85%88%E7%BA%A7%E9%98%9F%E5%88%97

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

巴特西

c#实现优先级队列

最新文章

热门文章