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

　　上述 KeyedPriorityQueue<T K V> 類中T 是要存儲在這個帶鍵值的優先隊列中的數據的類型K 是鍵的數據類型V 是值的數據類型

　　Dictionary<K int> keys 字段用於存儲鍵(K)在堆(heap)中的索引

　　bool ContainsKey(K key) 方法用於查找指定的鍵是否在該優先隊列中

　　Update(T v) 方法用於更新指定項目的值注意如果要使用這個方法的話T 不能是值類型之所以在這個方法的第二行:

　　if (typeof(T)IsValueType) throw new InvalidOperationException(T 不能是值類型);

　　進行這個判斷而不是在將該類聲明為

　　class KeyedPriorityQueue<T K V> where T : class { }

　　這是因為如果不需要調用 Update(T v) 方法的話T 還是允許是值類型的

　　該類的其他方面除了加入對 keys 字段的處理以外就和標准的優先隊列差不多了

　　有了這個 KeyedPriorityQueue<T K V> 類就可以從中派生出 PriorityQueue<T> 類來

class　PriorityQueue<T>　:　KeyedPriorityQueue<T　object　object>
{
　public　PriorityQueue()　:　base(null)　{　}
　public　PriorityQueue(int　capacity)　:　base(capacity　null)　{　}
　public　PriorityQueue(IComparer<T>　comparer)　:　base(comparer　null)　{　}
　public　PriorityQueue(int　capacity　IComparer<T>　comparer)　:　base(capacity　comparer　null)　{　}
}

　　對於 PriorityQueue<T> 類的實例如果調用 ContainsKey 方法總是返回 false如果調用 Update 方法總是引發 NotSupportedException 異常

　　現在讓我們回到上一篇隨筆 Timus Memory management 中需要稍微修改一下我們的內存管理器程序

　　首先Block 必須從結構改為類如下所示

sealed　class　Block
{
　public　int　Id　{　get;　private　set;　}
　public　int　Time　{　get;　set;　}
　public　Block(int　id　int　time)　{　Id　=　id;　Time　=　time;　}
}

　　然後需要一個實現 IKeyValue<T K V> 接口的類

sealed　class　IdTime　:　IKeyValue<Block　int　int>
{
　public　int　GetKey(Block　x)　{　return　xId;　}
　public　int　GetValue(Block　x)　{　return　xTime;　}
　public　void　SetValue(Block　x　int　v)　{　xTime　=　v;　}
}

　　最後就剩下最簡單的工作了將 Main 方法的第二行

　　var used = new KeyedPriorityQueue(new TimeComparer());

　　修改為

　　var used = new KeyedPriorityQueue<Block int int>(new TimeComparer() new IdTime());

　　就可以了

　　當然這也是有代價的就是運行時間和內存使用都增加了

ID Date Author Problem Language Judgement

　　result

Execution

　　time

Memory

　　used

:: Apr skyivben C# Accepted KB :: Apr skyivben C# Accepted KB

　　上表中第二行就是上一篇隨筆中的程序提交的結果第一行就是按照本篇隨筆修改後的程序提交的結果

　　實際上雖然 KeyedPriorityQueue 類中的代碼與 PriorityQueue<T> 類中代碼有大量的重復可以用本篇隨筆的方法將 KeyedPriorityQueue 類改為 KeyedPriorityQueue<T K V> 泛型類再從中派生出 PriorityQueue<T> 類來以消除重復的代碼但是這樣必然造成 PriorityQueue<T> 類的運行效率降低所以一般情況下PriorityQueue<T> 類還是使用原來的代碼為好

　　當然如果能夠從 PriorityQueue<T> 類派生出 KeyedPriorityQueue<T K V> 類那就比較完美了不知各位大俠是否還有更好的方法？

[]  []  

From:http://tw.wingwit.com/Article/program/net/201311/15448.html