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

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

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