程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> 關於C# >> 用C#實現優先隊列

用C#實現優先隊列

編輯:關於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)。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved