I am looking for a .NET implementation of a priority queue or heap data structure

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

Unless I am looking in the wrong place, there isn't one in the framework. Is anyone aware of a good one, or should I roll my own?

I like using the `OrderedBag`

and `OrderedSet`

classes in PowerCollections as priority queues.

You might like IntervalHeap from the C5 Generic Collection Library. To quote the user guide

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.

The API is simple enough

```
> var heap = new C5.IntervalHeap<int>();
> heap.Add(10);
> heap.Add(5);
> heap.FindMin();
5
```

Install from Nuget https://www.nuget.org/packages/C5 or GitHub https://github.com/sestoft/C5/

Licensed under: CC-BY-SA with attribution

Not affiliated with: Stack Overflow