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

用 C# 實現帶鍵值的優先隊列[1]

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

  首先需要一個接口用來獲取鍵以及獲取和設置值如下所示

namespace SkyivUtil
{
 interface IKeyValue<T K V>
 {
  K GetKey(T x);
  V GetValue(T x);
  void SetValue(T x V v);
 }
}

  接著就是我們的帶鍵值的優先隊列 KeyedPriorityQueue<T K V> 登場了

using System;
using SystemCollectionsGeneric;

namespace SkyivUtil
{
 class KeyedPriorityQueue<T K V>
 {
  IComparer<T> comparer;
  IKeyValue<T K V> kver;
  Dictionary<K int> keys;
  bool hasKey;
  T[] heap;

  public int Count { get; private set; }
  public KeyedPriorityQueue(IKeyValue<T K V> kv) : this(null kv) { }
  public KeyedPriorityQueue(int capacity IKeyValue<T K V> kv) : this(capacity null kv) { }
  public KeyedPriorityQueue(IComparer<T> comparer IKeyValue<T K V> kv) : this( comparer kv) { }

  public KeyedPriorityQueue(int capacity IComparer<T> comparer IKeyValue<T K V> kver)
  {
   thiskeys = new Dictionary<K int>();
   thiscomparer = (comparer == null) ? Comparer<T>Default : comparer;
   thiskver = kver;
   thishasKey = (kver != null);
   thisheap = new T[capacity];
  }

  public bool ContainsKey(K key)
  {
   return keysContainsKey(key);
  }

  public void Update(T v)
  {
   if (!hasKey) throw new NotSupportedException();
   if (typeof(T)IsValueType) throw new InvalidOperationException(T 不能是值類型);
   if (!ContainsKey(kverGetKey(v))) throw new ArgumentOutOfRangeException(v v 更新優先隊列時無此健值);
   var id = keys[kverGetKey(v)];
   var cmp = comparerCompare(v heap[id]);
   kverSetValue(heap[id] kverGetValue(v)); // 注意: 這一句要求 T 是引用類型不能是值類型
    if (cmp < ) SiftDown(id);
   else if (cmp > ) SiftUp(id);
  }

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

  public T Pop()
  {
   var v = Top();
   if (hasKey) keysRemove(kverGetKey(v));
   heap[] = heap[Count];
   if (Count > ) SiftDown(hasKey ? (keys[kverGetKey(heap[])] = ) : );
   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[hasKey ? (keys[kverGetKey(heap[n])] = n) : n] = heap[n];
   heap[hasKey ? (keys[kverGetKey(v)] = n) : 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[hasKey ? (keys[kverGetKey(heap[n])] = n) : n] = heap[n];
   }
   heap[hasKey ? (keys[kverGetKey(v)] = n) : n] = v;
  }
 }
}

[]  []  


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