用C#实现带键值的优先队列

用C#实现带键值的优先队列2011-06-26 博客园银河首先，需要一个接口，用来获取键以及获取和设置值，如下所示：

namespace Skyiv.Util
{
 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 System.Collections.Generic;

namespace Skyiv.Util
{
 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（16, comparer, kv） { }

  public KeyedPriorityQueue（int capacity, IComparer<T> comparer, IKeyValue<T, K, V> kver）
  {
   this.keys = new Dictionary<K, int>（）;
   this.comparer = （comparer == null） ？ Comparer<T>.Default : comparer;
   this.kver = kver;
   this.hasKey = （kver ！= null）;
   this.heap = new T[capacity];
  }

  public bool ContainsKey（K key）
  {
   return keys.ContainsKey（key）;
  }

  public void Update（T v）
  {
   if （！hasKey） throw new NotSupportedException（）;
   if （typeof（T）.IsValueType） throw new InvalidOperationException（"T 不能是值类型"）;
   if （！ContainsKey（kver.GetKey（v））） throw new ArgumentOutOfRangeException（"v", v, "更新优先队列时无此健值"）;
   var id = keys[kver.GetKey（v）];
   var cmp = comparer.Compare（v, heap[id]）;
   kver.SetValue（heap[id], kver.GetValue（v））; // 注意: 这一句要求 T 是引用类型，不能是值类型
    if （cmp < 0） SiftDown（id）;
   else if （cmp > 0） SiftUp（id）;
  }

  public void Push（T v）
  {
   if （Count >= heap.Length） Array.Resize（ref heap, Count * 2）;
   if （hasKey） keys[kver.GetKey（v）] = Count;
   heap[Count] = v;
   SiftUp（Count++）;
  }

  public T Pop（）
  {
   var v = Top（）;
   if （hasKey） keys.Remove（kver.GetKey（v））;
   heap[0] = heap[--Count];
   if （Count > 0） SiftDown（hasKey ？ （keys[kver.GetKey（heap[0]）] = 0） : 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[hasKey ？ （keys[kver.GetKey（heap[n2]）] = n） : n] = heap[n2];
   heap[hasKey ？ （keys[kver.GetKey（v）] = n） : 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[hasKey ？ （keys[kver.GetKey（heap[n2]）] = n） : n] = heap[n2];
   }
   heap[hasKey ？ （keys[kver.GetKey（v）] = n） : n] = v;
  }
 }
}