Why doesn't the .Net framework have a priority queue class?

Question

There are some threads on Stack Overflow dealing with implementing priority queues in .Net and C#.

My issue is of a more basic nature: Why isn't there a priority queue out of the box in the .Net framework? Even the C++ Standard Library has one.

Unlike

One of the first things I noticed when moving from Java to C#. No priority queue? Java even had/has synchronized priority queues. – Mella

see also https://mcmap.net/q/116367/-priority-queue-in-net-closed – Cano

Answer 1

There was a question a while ago (why C# does allow non-member functions like C++) which prompted Eric Lippert to write a blog post about the reasons why. In it, he explains:

I am asked "why doesn't C# implement feature X?" all the time. The answer is always the same: because no one ever designed, specified, implemented, tested, documented and shipped that feature. All six of those things are necessary to make a feature happen. All of them cost huge amounts of time, effort and money. Features are not cheap, and we try very hard to make sure that we are only shipping those features which give the best possible benefits to our users given our constrained time, effort and money budgets.

I suspect that is probably the answer to why .Net does not ship with a priority queue - there was just not enough time, effort, money, demand(?) to implement one.

Petronille

Thanks, Adrian, I read that blog post back when he wrote it. I'm also interested to hear the opinions of non-MS folks - is that data structure not actually needed in a framework? is it trivial enough to leave out for all other devs to implement on their own? etc. I know MY standpoint, but I can adjust on the basis of other's input. :-) – Unlike

Time is a question of priorities. If they say that there wasn't enough time, then the question becomes:"Why not include a priority queue, but do include xxx?" And xxx can be something less used than a priority queue. I dunno, maybe take xxx=HybridDictionary. I'm sure they've got something that could have been left out to make time for the priority queue. – Calycle

Yes, that's precisely what I meant, but you formulated it better... ;-) – Unlike

One thing to bear in mind is that the framework itself utilises the contents of the framework. Taking your example: if you look at the usages of HybridDictionary, it is used a lot by the internals of framework (especially by System.Windows.* and System.Web.*). Not needing a HybridDictionary as a consumer of the framework (and hence not seeing it as high a priority as a priority queue) doesn't necessarily mean that HybridDictionary should have been omitted - it was probably needed to implement the internals and so was exposed publicly. – Petronille

See this: github.com/dotnet/runtime/issues/14032#issuecomment-656700280, they take 5 years, still no PriorityQueue. – Maurer

Answer 2

.NET 4.0 introduces a SortedSet<T> class, along with the ISet<T> interface which is implemented by SortedSet<T> and HashSet<T>. This will obviously make it simpler to implement your own PriorityQueue<T> class.

However, there is still no IQueue<T> interface, which would at least admit the need for priority queues or any other implementation than the basic BCL Queue<T>. Similarly, there's no IStack<T>.

Personally I find this lack of some of these most basic interfaces disappointing and short-sighted, especially as the design/specification/implementation/testing/documentation cost of extracting a simple interface from an existing class should be very low indeed.

public interface IQueue<T> : IEnumerable<T>, ICollection, IEnumerable
{
    T Dequeue();
    void Enqueue(T item);
    T Peek();
}

There, see? I've done it.

Dirac

You've coded the interface, but what about the class? There aren't many interfaces in .Net that don't come with at least one implementation. – Matthewmatthews

Would that interface be usable by non-enumerable queues, like asynchronous communication queues? What about queue endpoints, should they have their own interfaces, so that you can give only push-capability to one part of the code, and pull-capability to another? The problem isn't writing those 5 lines of code, the problem is designing it so that nobody complains, and it produces value for the .NET runtime in the process. – Quacksalver

ck: see System.Collections.Generic.Queue<T> Lasse: asynchronous/concurrent collections don't have the same behaviourial contract, so they'd have no need to implement the interface. My point is that the BCL team attitude seems to be that if they only provide one implementation of a construct, there is no need for an interface, which is not the correct attitude. IMHO. – Dirac

Answer 3

This has been officially announced and is in the .NET 6 preview.

PriorityQueue<TElement, TPriority> (System.Collections.Generic) is a new collection that enables adding new items with a value and a priority. On dequeue the PriorityQueue returns the element with the lowest priority value. You can think of this new collection as similar to Queue but that each enqueued element has a priority value that affects the behavior of dequeue.

The following sample demonstrates the behavior of PriorityQueue<string, int>.

// creates a priority queue of strings with integer priorities
var pq = new PriorityQueue<string, int>();

// enqueue elements with associated priorities
pq.Enqueue("A", 3);
pq.Enqueue("B", 1);
pq.Enqueue("C", 2);
pq.Enqueue("D", 3);

pq.Dequeue(); // returns "B"
pq.Dequeue(); // returns "C"
pq.Dequeue(); // either "A" or "D", stability is not guaranteed.

Pennon

Answer 4

As of January 2021, .Net Core added a PriorityQueue implementation. The actual commit to the repo and the API can be found here: https://github.com/dotnet/runtime/commit/826aa4f7844fd3d48784025ec6d47010867baab4

Vieva

Answer 5

It's available as part of .NET6 now. Check out the following blog post for implementation.

https://dotnetcoretutorials.com/2021/03/17/priorityqueue-in-net/

Miserere