C#中的简单优先级队列 – 什么比使用自定义排序器的List更好：IC

发布时间：2020-12-16 00:06:21 所属栏目：百科来源：网络整理

导读：我想实现一个优先级队列,它将注入我的对象 – 关于一个字段的节点 – f.我已经用自定义比较器编写了List,但这需要我： enqueue – 每次插入后对List进行排序 dequeue – 删除最后一个(而不是第一个表现),如此 myList.RemoveAt(myList.Count - 1); 我的列表应

我想实现一个优先级队列,它将注入我的对象 – 关于一个字段的节点 – f.我已经用自定义比较器编写了List,但这需要我：

> enqueue – 每次插入后对List进行排序
> dequeue – 删除最后一个(而不是第一个表现),如此

myList.RemoveAt(myList.Count - 1);

我的列表应该总是根据某个字段排序(这里我需要它按f排序).我还需要能够使用列表中最低值的对象添加和出列.

有人能告诉我最好的办法是什么？

编辑

dasblinkenlight有一个非常好的答案,但我已经意识到我应该能够在这个容器中存储重复项.

解决方法

如果您使用的是.NET 4或更高版本,则可以将 SortedSet<T>类与自定义IComparer< T>一起使用.

该类允许您使用所有可变集合通用的Add方法添加新对象.您可以使用Max属性检索max元素,然后调用Remove删除集合中的max.

编辑:(响应编辑的问题)如果您需要存储重复项,您可以使用SortedDictionary<Key,int>,并从中计算出一个计数集.同样,您可以选择使用自定义IComparer< T>.将元素排入队列时,检查它是否已存在,并增加其计数.出列时,再次检查计数,递减计数,并仅在计数达到零时移除密钥.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!