Tôi tin rằng một SortedSet<KeyValuePair<K,V>>
với một tuỳ chỉnh Comparer
sẽ thực hiện công việc.
Các Comparer
sẽ trông giống như sau:
class KeyValueComparer<K, V> : IComparer<KeyValuePair<K,V>> where K:IComparable where V:IComparable
{
public int Compare(KeyValuePair<K, V> x, KeyValuePair<K, V> y)
{
var res = x.Key.CompareTo(y.Key);
return res == 0 ? x.Value.CompareTo(y.Value) : res;
}
}
Với ví dụ Comparer
, các SortedSet
sẽ được sắp xếp theo Key và nó sẽ cho phép các bản sao của các phím.
Bạn có thể lấy Min
lúc liên tục, RemoveMin
tại O(logn)
, Add
một mục tại O(logn)
và Update
một chìa khóa tại O(logn)
.
Đây là một đầy đủ (hoặc hầu hết) thực hiện:
public class Heap<K, V>
where K : IComparable
where V : IComparable
{
private readonly SortedSet<KeyValuePair<K, V>> _sortedSet;
// O(1)
public KeyValuePair<K, V> Min
{
get { return _sortedSet.Min; }
}
public Heap()
{
_sortedSet = new SortedSet<KeyValuePair<K, V>>(new KeyValueComparer<K, V>());
}
// O(logn)
public void Add(K key, V value)
{
_sortedSet.Add(new KeyValuePair<K, V>(key, value));
}
// O(logn)
public KeyValuePair<K, V> RemoveMin()
{
var min = Min;
_sortedSet.Remove(min);
return min;
}
// O(logn)
public void Remove(K key, V value)
{
_sortedSet.Remove(new KeyValuePair<K, V>(key, value));
}
// O(logn)
public void UpdateKey(K oldKey, V oldValue, K newKey)
{
Remove(oldKey, oldValue);
Add(newKey, oldValue);
}
private class KeyValueComparer<K, V> : IComparer<KeyValuePair<K, V>>
where K : IComparable
where V : IComparable
{
public int Compare(KeyValuePair<K, V> x, KeyValuePair<K, V> y)
{
var res = x.Key.CompareTo(y.Key);
return res == 0 ? x.Value.CompareTo(y.Value) : res;
}
}
}
Chỉ cần tò mò, những gì bạn đang viết một đống gì? – core
http://stackoverflow.com/a/13776636/67824 –
Xem thêm https://stackoverflow.com/questions/102398/priority-queue-in-net –