用 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> 类来

classPriorityQueue<T>:KeyedPriorityQueue<Tobjectobject>

{

publicPriorityQueue():base(null){}

publicPriorityQueue(intcapacity):base(capacitynull){}

publicPriorityQueue(IComparer<T>comparer):base(comparernull){}

publicPriorityQueue(intcapacityIComparer<T>comparer):base(capacitycomparernull){}

}

对于 PriorityQueue<T> 类的实例如果调用 ContainsKey 方法总是返回 false如果调用 Update 方法总是引发 NotSupportedException 异常

现在让我们回到上一篇随笔 Timus Memory management 中需要稍微修改一下我们的内存管理器程序

首先Block 必须从结构改为类如下所示

sealedclassBlock

{

publicintId{get;privateset;}

publicintTime{get;set;}

publicBlock(intidinttime){Id=id;Time=time;}

}

然后需要一个实现 IKeyValue<T K V> 接口的类

sealedclassIdTime:IKeyValue<Blockintint>

{

publicintGetKey(Blockx){returnxId;}

publicintGetValue(Blockx){returnxTime;}

publicvoidSetValue(Blockxintv){xTime=v;}

}

最后就剩下最简单的工作了将 Main 方法的第二行

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

修改为

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

就可以了

当然这也是有代价的就是运行时间和内存使用都增加了