Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

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.

like image 280
Johann Gerell Avatar asked Dec 14 '09 09:12

Johann Gerell


People also ask

Why there is no priority queue in C#?

Priority Queue is just a queue, with a twist. While the dequeuing order in a regular queue depends on the enqueuing precedence – First In First Out (FIFO), in a priority queue it depends on the priority of the element. In other words, the element that has the highest priority is dequeued first.

Does C# have a built in priority queue?

A priority queue assigns a priority to each element. Knowing how to build them is important in solving many coding problems. A priority queue is a data structure that holds information that has some sort of priority value.

Does Javascript have priority queue?

Priority Queue is an extension of Queue having some properties as follows: Each element of the priority queue has a priority associated with it.

Is priority queue better than sorting?

Inserting n items into a priority queue will have asymptotic complexity O(n log n) so in terms of complexity, it's not more efficient than using sort once, at the end.


2 Answers

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.

like image 128
adrianbanks Avatar answered Oct 07 '22 21:10

adrianbanks


.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.

like image 26
Mark Rendle Avatar answered Oct 07 '22 23:10

Mark Rendle