.Net中的优先级队列
时间:2020-03-06 14:26:15 来源:igfitidea点击:
我正在寻找优先级队列或者堆数据结构的.NET实现
Priority queues are data structures that provide more flexibility than simple sorting, because they allow new elements to enter a system at arbitrary intervals. It is much more cost-effective to insert a new job into a priority queue than to re-sort everything on each such arrival. The basic priority queue supports three primary operations: Insert(Q,x). Given an item x with key k, insert it into the priority queue Q. Find-Minimum(Q). Return a pointer to the item whose key value is smaller than any other key in the priority queue Q. Delete-Minimum(Q). Remove the item from the priority queue Q whose key is minimum
除非我在错误的地方寻找,否则框架中没有一个。有谁知道一个好人,还是我应该自己滚一个人?
解决方案
我喜欢将PowerCollections中的OrderedBag和OrderedSet类用作优先级队列。
在Java Collections框架中的Java实现(java.util.PriorityQueue)上使用Java到Ctranslator,或者更智能地使用算法和核心代码,并将其插入我们自己制作的Cclass中,该Cclass符合Queues的CCollections框架API。 ,或者至少是收藏集。
我在Julian Bucknall的http://www.boyet.com/Articles/PriorityQueueCSharp3.html博客上找到了一个
我们对其进行了稍微的修改,以使队列中的低优先级项目最终会随着时间的流逝而"泡沫化"到顶部,因此它们不会遭受饥饿。
我们可能喜欢C5通用收藏库中的IntervalHeap。引用用户指南
Class IntervalHeap<T> implements interface IPriorityQueue<T> using an interval heap stored as an array of pairs. The FindMin and FindMax operations, and the indexer’s get-accessor, take time O(1). The DeleteMin, DeleteMax, Add and Update operations, and the indexer’s set-accessor, take time O(log n). In contrast to an ordinary priority queue, an interval heap offers both minimum and maximum operations with the same efficiency.
API足够简单
> var heap = new C5.IntervalHeap<int>(); > heap.Add(10); > heap.Add(5); > heap.FindMin(); 5
从Nuget https://www.nuget.org/packages/C5或者GitHub https://github.com/sestoft/C5/安装
我们可能会发现此实现有用:
http://www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx
它是通用的,基于堆数据结构