.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

它是通用的,基于堆数据结构