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

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

namespaceSkyivUtil

{

interfaceIKeyValue<TKV>

{

KGetKey(Tx);

VGetValue(Tx);

voidSetValue(TxVv);

}

}

接着就是我们的带键值的优先队列 KeyedPriorityQueue<T K V> 登场了

usingSystem;

usingSystemCollectionsGeneric;

namespaceSkyivUtil

{

classKeyedPriorityQueue<TKV>

{

IComparer<T>comparer;

IKeyValue<TKV>kver;

Dictionary<Kint>keys;

boolhasKey;

T[]heap;

publicintCount{get;privateset;}

publicKeyedPriorityQueue(IKeyValue<TKV>kv):this(nullkv){}

publicKeyedPriorityQueue(intcapacityIKeyValue<TKV>kv):this(capacitynullkv){}

publicKeyedPriorityQueue(IComparer<T>comparerIKeyValue<TKV>kv):this(comparerkv){}

publicKeyedPriorityQueue(intcapacityIComparer<T>comparerIKeyValue<TKV>kver)

{

thiskeys=newDictionary<Kint>();

thiscomparer=(comparer==null)?Comparer<T>Default:comparer;

thiskver=kver;

thishasKey=(kver!=null);

thisheap=newT[capacity];

}

publicboolContainsKey(Kkey)

{

returnkeysContainsKey(key);

}

publicvoidUpdate(Tv)

{

if(!hasKey)thrownewNotSupportedException();

if(typeof(T)IsValueType)thrownewInvalidOperationException(T不能是值类型);

if(!ContainsKey(kverGetKey(v)))thrownewArgumentOutOfRangeException(vv更新优先队列时无此健值);

varid=keys[kverGetKey(v)];

varcmp=comparerCompare(vheap[id]);

kverSetValue(heap[id]kverGetValue(v));//注意:这一句要求T是引用类型不能是值类型

if(cmp<)SiftDown(id);

elseif(cmp>)SiftUp(id);

}

publicvoidPush(Tv)

{

if(Count>=heapLength)ArrayResize(refheapCount*);

if(hasKey)keys[kverGetKey(v)]=Count;

heap[Count]=v;

SiftUp(Count++);

}

publicTPop()

{

varv=Top();

if(hasKey)keysRemove(kverGetKey(v));

heap[]=heap[Count];

if(Count>)SiftDown(hasKey?(keys[kverGetKey(heap[])]=):);

returnv;

}

publicTTop()

{

if(Count>)returnheap[];

thrownewInvalidOperationException(优先队列为空);

}

voidSiftUp(intn)

{

varv=heap[n];

for(varn=n/;n>&&comparerCompare(vheap[n])>;n=nn/=)

heap[hasKey?(keys[kverGetKey(heap[n])]=n):n]=heap[n];

heap[hasKey?(keys[kverGetKey(v)]=n):n]=v;

}

voidSiftDown(intn)

{

varv=heap[n];

for(varn=n*;n<Count;n=nn*=)

{

if(n+<Count&&comparerCompare(heap[n+]heap[n])>)n++;

if(comparerCompare(vheap[n])>=)break;

heap[hasKey?(keys[kverGetKey(heap[n])]=n):n]=heap[n];

}

heap[hasKey?(keys[kverGetKey(v)]=n):n]=v;

}

}

}

[] []