用C#實現帶鍵值的優先隊列（1）

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

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;
　　}
　}
}