Add priority queue to generic collections

[thoren-d]

I see the generic collections haven't been incorporating into this project yet, but when that happens, I'd like to contribute a priority queue to the library. It's a pretty commonly used data structure and I'm surprised there isn't one in there already.

What I've got is based on a flat binary heap and either uses items that implement IComparable or takes an IComparer.

[dilijev]

My understanding is that some datastructures already use PQ internally, but I could very well be mistaken about this. The documentation isn't especially clear on this point.

[karldodd]

Will be a nice API addition :) Java has had its PriorityQueue for quite some time.

Even better if there is a thread-safe concurrent priority queue under System.Collections.Concurrent.

[colombod]

I totally like @karldodd suggestion, would love to contribute!

[ebickle]

Absolutely agree. I have my own person implementation of a priority queue in C#, if we want to use it as a starting point. This is a data structure that's been sorely needed for a long time.

'Priority queue' is the traditional name for the data structure, but if you look at the existing naming conventions for collections in .NET they use more user-friendly names. Perhaps SortedQueue, to match SortedDictionary<TKey, TValue> and SortedSet?

My current API looks a bit like this:

public class PriorityQueue<T>
{
    public PriorityQueue();
    public PriorityQueue(Comparison<T>);
    public PriorityQueue(IComparer<T>);
    public PriorityQueue(IEnumerable<T>);
    public PriorityQueue(IEnumerable<T>, Comparison<T>);
    public PriorityQueue(IEnumerable<T>, IComparer<T>);
    public bool IsEmpty { get; }
    public int Count { get; }
    public void Enqueue(T item);
    public T Dequeue();
    public T Peek();
    public void CopyTo(T[] array, int index);
    public T[] ToArray();
} 

Will need to add ICollection, IReadOnlyCollection, IEnumerable, and IEnumerable at very least. Constructors to set the initial capacity as well.

Open to drafting up an API proposal.

[stephentoub]

Closing to consolidate with same feature being requested in detail in dotnet/corefx#574

[hickford]

Data structures are the fundamental primitives of algorithm design. It's important for the standard library to have fast reliable well-documented implementations. Otherwise developers waste time reinventing the wheel.

.NET is desperately missing a priority queue, please add one.

[colombod]

I think priority queue are implemented in top of the sorted collection.

On 27 Nov 2015, at 14:32, Mirth Hickford notifications@github.com wrote:

Data structures are the fundamental primitives of algorithm design. It's important for the standard library to have fast reliable well-documented implementations. Otherwise developers waste time reinventing the wheel.

.NET is desperately missing a priority queue, please add one.

—
Reply to this email directly or view it on GitHub.