.NET中的堆类
可能重复：
c＃中的Fibonacci，Binary或Binomial堆？
在.NET中是否有像堆这样的类？ 我需要某种收集，我可以从中检索最小值。 元件。 我只想要3种方法：
- 加（）
- RemoveMinElement（）
- GetMinElement（）
我不能使用排序列表，因为键必须是唯一的，我可能有几个相同的元素。
您可以使用自定义键使用SortedList或SortedDictionary （请参阅下面的讨论）。 如果您使用具有引用相等性的类型，但可以根据您关注的值进行比较，那么这可能有效。
像这样的东西：
class HeapKey : IComparable { public HeapKey(Guid id, Int32 value) { Id = id; Value = value; } public Guid Id { get; private set; } public Int32 Value { get; private set; } public int CompareTo(HeapKey other) { if (_enableCompareCount) { ++_compareCount; } if (other == null) { throw new ArgumentNullException("other"); } var result = Value.CompareTo(other.Value); return result == 0 ? Id.CompareTo(other.Id) : result; } }
以下是使用具有二进制堆性能特征的SortedDictionary的工作示例：
using System; using System.Collections.Generic; using System.Linq; namespace SortedDictionaryAsBinaryHeap { class Program { private static Boolean _enableCompareCount = false; private static Int32 _compareCount = 0; static void Main(string[] args) { var rnd = new Random(); for (int elementCount = 2; elementCount <= 6; elementCount++) { var keyValues = Enumerable.Range(0, (Int32)Math.Pow(10, elementCount)) .Select(i => new HeapKey(Guid.NewGuid(), rnd.Next(0, 10))) .ToDictionary(k => k); var heap = new SortedDictionary(keyValues); _compareCount = 0; _enableCompareCount = true; var min = heap.First().Key; _enableCompareCount = false; Console.WriteLine("Element count: {0}; Compare count for getMinElement: {1}", (Int32)Math.Pow(10, elementCount), _compareCount); _compareCount = 0; _enableCompareCount = true; heap.Remove(min); _enableCompareCount = false; Console.WriteLine("Element count: {0}; Compare count for deleteMinElement: {1}", (Int32)Math.Pow(10, elementCount), _compareCount); } Console.ReadKey(); } private class HeapKey : IComparable { public HeapKey(Guid id, Int32 value) { Id = id; Value = value; } public Guid Id { get; private set; } public Int32 Value { get; private set; } public int CompareTo(HeapKey other) { if (_enableCompareCount) { ++_compareCount; } if (other == null) { throw new ArgumentNullException("other"); } var result = Value.CompareTo(other.Value); return result == 0 ? Id.CompareTo(other.Id) : result; } } } }
结果：
元素数：100; 比较getMinElement的计数：0
元素数：100; 比较deleteMinElement的计数：8
元素数：1000; 比较getMinElement的计数：0
元素数：1000; 比较deleteMinElement的计数：10
元素数：10000; 比较getMinElement的计数：0
元素数：10000; 比较deleteMinElement的计数：13
元素数：100000; 比较getMinElement的计数：0
元素数：100000; 比较deleteMinElement的计数：14
元素数：1000000; 比较getMinElement的计数：0
元素数：1000000; 比较deleteMinElement的计数：21
优先级队列看起来非常适合您的问题： .Net中的优先级队列
Google针对“C＃优先级队列”进行了更多实施。