在上一篇随笔 Timus 1037. Memory management 的“进一步的讨论”小节中，我提到：
这个程序中使用 KeyedPriorityQueue 来存储已分配的“内存块”，使用 PriorityQueue 来存储尚未分配的“自由块”。这两个优先队列的算法是一样的，可以想办法合并。这将在下一篇随笔中讨论。
现在，就开始行动吧。
首先，需要一个接口，用来获取键以及获取和设置值，如下所示：
namespace Skyiv.Util{ interface IKeyValue { K GetKey(T x); V GetValue(T x); void SetValue(T x, V v); }}
接着，就是我们的带键值的优先队列 KeyedPriorityQueue 登场了：
using System;using System.
Collections.Generic;namespace Skyiv.Util{ class KeyedPriorityQueue { IComparer comparer; IKeyValue kver; Dictionaryint> keys; bool hasKey; T[] heap; public int Count { get; private set; } public KeyedPriorityQueue(IKeyValue kv) : this(null, kv) { } public KeyedPriorityQueue(int capacity, IKeyValue kv) : this(capacity, null, kv) { } public KeyedPriorityQueue(IComparer comparer, IKeyValue kv) : this(16, comparer, kv) { } public KeyedPriorityQueue(int capacity, IComparer comparer, IKeyValue kver) { this.keys = new Dictionaryint>(); this.comparer = (comparer == null) ? Comparer.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; } }}
上述 KeyedPriorityQueue 类中，T 是要存储在这个带键值的优先队列中的数据的类型，K 是键的数据类型，V 是值的数据类型。
Dictionaryint> keys 字段用于存储键(K)在堆(heap)中的索引。
bool ContainsKey(K key) 方法用于查找指定的键是否在该优先队列中。
Update(T v) 方法用于更新指定项目的值。注意，如果要使用这个方法的话，T 不能是值类型。之所以在这个方法的第二行:
if (typeof(T).IsValueType) throw new InvalidOperationException("T 不能是值类型");
进行这个判断，而不是在将该类声明为：
class KeyedPriorityQueue where T : class { ... }
这是因为，如果不需要调用 Update(T v) 方法的话，T 还是允许是值类型的。
该类的其他方面，除了加入对 keys 字段的处理以外，就和标准的优先队列差不多了。
有了这个 KeyedPriorityQueue 类，就可以从中派生出 PriorityQueue 类来：
class PriorityQueue : KeyedPriorityQueueobject, object>{ public PriorityQueue() : base(null) { } public PriorityQueue(int capacity) : base(capacity, null) { } public PriorityQueue(IComparer comparer) : base(comparer, null) { } public PriorityQueue(int capacity, IComparer comparer) : base(capacity, comparer, null) { }}
对于 PriorityQueue 类的实例，如果调用 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; }}
然后，需要一个实现 IKeyValue 接口的类：
sealed class IdTime : IKeyValue<Block, int, int>{ public int GetKey(Block x) { return x.Id; } public int GetValue(Block x) { return x.Time; } public void SetValue(Block x, int v) { x.Time = 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 2568007 21:22:09 18 Apr 2009 skyivben 1037 C# Accepted 0.406 6 129 KB 2566773 09:24:17 18 Apr 2009 skyivben 1037 C# Accepted 0.265 4 521 KB
上表中第二行就是上一篇随笔中的程序提交的结果，第一行就是按照本篇随笔修改后的程序提交的结果。
实际上，虽然 KeyedPriorityQueue 类中的代码与 PriorityQueue 类中代码有大量的重复，可以用本篇随笔的方法将 KeyedPriorityQueue 类改为 KeyedPriorityQueue 泛型类，再从中派生出 PriorityQueue 类来，以消除重复的代码。但是，这样必然造成 PriorityQueue 类的运行效率降低。所以，一般情况下，PriorityQueue 类还是使用原来的代码为好。
当然，如果能够从 PriorityQueue 类派生出 KeyedPriorityQueue 类，那就比较完美了。不知各位大侠是否还有更好的方法？