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

在 KeyedPriorityQueue<T, K, V> 類中，T 代表儲存於隊列中的資料型別，K 為鍵的型別，V 為值的型別。

Dictionary<K, int> keys 欄位用於記錄鍵在堆積中的索引位置。

bool ContainsKey(K key) 方法可檢查指定鍵是否存在於優先隊列中。

Update(T v) 方法用於更新指定項目的值。請注意，若要使用此方法，T 不能是實值型別。因此在方法開頭會進行判斷：

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

之所以不在類別宣告時直接限制 where T : class，是因為若不呼叫 Update 方法，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 1037. 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; }
}