C#中的简单优先级队列 – 什么比使用自定义Sorter的List更好:IComparer?
我想实现一个优先级队列,它将注入我的对象 – 关于一个字段的Nodes
– f
。 我已经用自定义比较器编写了List,但这需要我:
我的列表应该总是根据某个字段排序(这里我需要它按f
排序)。 我还需要能够使用列表中的最小值添加和dequeue
列对象。
有人能告诉我这是最好的方法吗?
编辑
dasblinkenlight有一个非常好的答案,但我已经意识到我应该能够在这个容器中存储重复项。
如果您使用的是.NET 4或更高版本,则可以将SortedSet
类与自定义IComparer
。
该类允许您使用所有可变集合通用的Add
方法添加新对象。 您可以使用Max
属性检索max元素,然后调用Remove
删除集合中的max。
编辑:(响应对问题的编辑)如果需要存储重复项,可以使用SortedDictionary
,并从中创建计数集。 同样,您可以选择使用自定义IComparer
。 排队元素时,检查它是否已存在,并增加其计数。 出列时,再次检查计数,递减计数,并仅在计数达到零时移除密钥。
如前所述, SortedDictionary
可以帮助您实现目标,只需要一种处理重复优先级的方法。 在任何基于Map的结构( Dictionary
, SortedDictionary
等)中处理重复项的方法是使值成为您真正想要的值的集合。 在您的情况下,最有意义的是值为Queue
。
这是一个起点。 如果需要,您可以添加其他方法,如Count
, IEnumerable
实现等。
上述就是C#学习教程:C#中的简单优先级队列 – 什么比使用自定义Sorter的List更好:IComparer?分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注—计算机技术网(www.ctvol.com)!
/// /// /// /// The type of the actual elements that are stored /// The type of the priority. It probably makes sense to be an int or long, /// but any type that can be the key of a SortedDictionary will do. public class PriorityQueue { private SortedDictionary> dictionary = new SortedDictionary>(); private Func selector; public PriorityQueue(Func selector) { this.selector = selector; } public void Enqueue(TElement item) { TKey key = selector(item); Queue queue; if (!dictionary.TryGetValue(key, out queue)) { queue = new Queue (); dictionary.Add(key, queue); } queue.Enqueue(item); } public TElement Dequeue() { if (dictionary.Count == 0) throw new Exception("No items to Dequeue:"); var key = dictionary.Keys.First(); var queue = dictionary[key]; var output = queue.Dequeue(); if (queue.Count == 0) dictionary.Remove(key); return output; } }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/cdevelopment/1013534.html