用堆实现优先队列 用 C# 实现带键值的优先队列[1]

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

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

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>　parer;　　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>　parer 　IKeyValue<T 　K 　V>　kv)　:　this( 　parer 　kv)　{　}

　　public　KeyedPriorityQueue(int　capacity 　IComparer<T>　parer 　IKeyValue<T 　K 　V>　kver)　　{　　　this keys　=　new　Dictionary<K 　int>();　　　this parer　=　(parer　==　null)　?　Comparer<T> Default　:　parer;　　　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　=　parer Compare(v 　heap[id]);　　　kver SetValue(heap[id] 　kver GetValue(v));　//　注意:　这一句要求　T　是引用类型 不能是值类型　　　　if　(cmp　<　 )　SiftDown(id);　　　else　if　(cmp　>　 )　SiftUp(id);　　}

　　public　void　Push(T　v)　　{　　　if　(Count　>=　heap Length)　Array Resize(ref　heap 　Count　*　 );　　　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[ ]　=　heap[ Count];　　　if　(Count　>　 )　SiftDown(hasKey　?　(keys[kver GetKey(heap[ ])]　=　 )　:　 );　　　return　v;　　}

　　public　T　Top()　　{　　　if　(Count　>　 )　return　heap[ ];　　　throw　new　InvalidOperationException( 优先队列为空 );　　}

　　void　SiftUp(int　n)　　{　　　var　v　=　heap[n];　　　for　(var　n 　=　n　/　 ;　n　>　 　&&　parer Compare(v 　heap[n ])　>　 ;　n　=　n 　n 　/=　 )　　　　heap[hasKey　?　(keys[kver GetKey(heap[n ])]　=　n)　:　n]　=　heap[n ];　　　heap[hasKey　?　(keys[kver GetKey(v)]　=　n)　:　n]　=　v;　　}

　　void　SiftDown(int　n)　　{　　　var　v　=　heap[n];　　　for　(var　n 　=　n　*　 ;　n 　<　Count;　n　=　n 　n 　*=　 )　　　{　　　　if　(n 　+　 　<　Count　&&　parer Compare(heap[n 　+　 ] 　heap[n ])　>　 )　n ++;　　　　if　(parer Compare(v 　heap[n ])　>=　 )　break;　　　　heap[hasKey　?　(keys[kver GetKey(heap[n ])]　=　n)　:　n]　=　heap[n ];　　　}　　　heap[hasKey　?　(keys[kver GetKey(v)]　=　n)　:　n]　=　v;　　}　}}

lishixinzhi/Article/program/net/201311/15449