熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> .NET編程 >> 正文

簡述用C#實現優先隊列方法

2013-11-13 12:12:03  來源: .NET編程 

  優先隊列(priority queue) 是很重要的數據結構我在做 ACM 題時就經常要用到她C++ STL 就包括 priority_queue Java 也有 PriorityQueue 類遺憾的是NET Framework Base Class Library 中並不包括優先隊列於是我只好自己用 C# 語言寫一個如下所示

using System;
using SystemCollectionsGeneric;

namespace SkyivUtil
{
 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( comparer) { }

  public PriorityQueue(int capacity IComparer<T> comparer)
  {
   thiscomparer = (comparer == null) ? Comparer<T>Default : comparer;
   thisheap = new T[capacity];
  }

  public void Push(T v)
  {
   if (Count >= heapLength) ArrayResize(ref heap Count * );
   heap[Count] = v;
   SiftUp(Count++);
  }

  public T Pop()
  {
   var v = Top();
   heap[] = heap[Count];
   if (Count > ) SiftDown();
   return v;
  }

  public T Top()
  {
   if (Count > ) return heap[];
   throw new InvalidOperationException(優先隊列為空);
  }

  void SiftUp(int n)
  {
   var v = heap[n];
   for (var n = n / ; n >  && comparerCompare(v heap[n]) > ; n = n n /= ) heap[n] = heap[n];
   heap[n] = v;
  }

  void SiftDown(int n)
  {
   var v = heap[n];
   for (var n = n * ; n < Count; n = n n *= )
   {
    if (n +  < Count && comparerCompare(heap[n + ] heap[n]) > ) n++;
    if (comparerCompare(v heap[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)


From:http://tw.wingwit.com/Article/program/net/201311/15388.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.