用 C# 实现带键值的优先队列

核心提示：首先，需要一个接口，用 C# 实现带键值的优先队列，用来获取键以及获取和设置值，如下所示：namespaceSkyiv.Util{interfaceIKeyValue<T,K,V>{KGetKey(Tx);VGetValue(Tx);voidSetValue(Tx,Vv);}}接着，当然，如果能够从 Pri

首先，需要一个接口，用来获取键以及获取和设置值，如下所示：

namespace　Skyiv.Util
{
　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　System.Collections.Generic;

namespace　Skyiv.Util
{
　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(16,　comparer,　kv)　{　}

　　public　KeyedPriorityQueue(int　capacity,　IComparer<T>　comparer,　IKeyValue<T,　K,　V>　kver)
　　{
　　　this.keys　=　new　Dictionary<K,　int>();
　　　this.comparer　=　(comparer　==　null)　?　Comparer<T>.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> 类中，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 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<T, K, V> 接口的类：

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<T> 类中代码有大量的重复，可以用本篇随笔的方法将 KeyedPriorityQueue 类改为 KeyedPriorityQueue<T, K, V> 泛型类，再从中派生出 PriorityQueue<T> 类来，以消除重复的代码。但是，这样必然造成 PriorityQueue<T> 类的运行效率降低。所以，一般情况下，PriorityQueue<T> 类还是使用原来的代码为好。

当然，如果能够从 PriorityQueue<T> 类派生出 KeyedPriorityQueue<T, K, V> 类，那就比较完美了。不知各位大侠是否还有更好的方法？