我正在寻找优先级队列或堆数据结构的.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

除非我找错地方了,否则框架里没有。有谁知道好的吗,还是我自己卷?


当前回答

. net 6+:正如@rustyx评论的那样,. net 6添加了System.Collections.Generic。PriorityQueue < TElement, TPriority >类。FWIW是开源的,用c#实现的。

早期的。net核心版本和。net框架:微软在。net框架中编写(并在线共享)了2个内部的PriorityQueue类。然而,正如@ mathumum -mut所评论的那样,其中有一个错误(SO社区当然已经提供了修复):微软内部PriorityQueue<T>?

其他回答

我喜欢使用PowerCollections中的OrderedBag和OrderedSet类作为优先队列。

在Java Collections框架中的Java实现(Java .util. priorityqueue)上使用Java到c#的转换器,或者更智能地使用算法和核心代码,并将其插入到您自己制作的c#类中,该类遵循c# Collections框架用于队列的API,或者至少是Collections。

我在Julian Bucknall的博客(http://www.boyet.com/Articles/PriorityQueueCSharp3.html)上找到了一个

我们稍微修改了一下,以便队列中优先级低的项目最终会随着时间的推移“上升”到顶部,这样它们就不会挨饿了。

. net 6+:正如@rustyx评论的那样,. net 6添加了System.Collections.Generic。PriorityQueue < TElement, TPriority >类。FWIW是开源的,用c#实现的。

早期的。net核心版本和。net框架:微软在。net框架中编写(并在线共享)了2个内部的PriorityQueue类。然而,正如@ mathumum -mut所评论的那样,其中有一个错误(SO社区当然已经提供了修复):微软内部PriorityQueue<T>?

你可能会喜欢C5泛型集合库中的IntervalHeap。引用用户指南

类IntervalHeap<T>使用存储为对数组的间隔堆实现接口IPriorityQueue<T>。FindMin和 FindMax操作和索引器的get-访问器花费的时间为O(1)。DeleteMin, DeleteMax、Add和Update操作,以及索引器的集访问器,都需要时间 O(log n)。与普通优先级队列相比,间隔堆提供了两个最小优先级队列 同样效率的最大操作。

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/安装