Priority Queue in .Net

Priority queue in .Net

I like using the OrderedBag and OrderedSet classes in PowerCollections as priority queues.

Can't use priority queue in C# .NET 6

The version reported by dotnet is completely unrelated to Unity's C#/.NET version (at least until Unity finally migrates from Mono). While the language supported is almost equal to C# 9.0, the actual library that is used is a loose superset of what Mono provides, and actually is roughly equal to .NET Framework 4.8/.NET Standard 2.0 ATM; since neither of those has PriorityQueue, it's not available. You can either:

• wait for the transition to .NET 6/7 happen (be aware it may take a couple of years :),
• use a 3rd party implementation,
• implement it yourself,
• copy-paste the code from the official source
  (minor tweaks will be required for it to work) or
• use this direct port from official C# lib
  (single-file drop-in, ported by me, open source, no string attached).

Is .NET 6 PriorityQueue thread-safe?

With a look at the source code for PriorityQueue.Enqueue, for instance, it is immediately apparent that the code is not thread-safe:

public void Enqueue(TElement element, TPriority priority)
{
    // Virtually add the node at the end of the underlying array.
    // Note that the node being enqueued does not need to be physically placed
    // there at this point, as such an assignment would be redundant.

    int currentSize = _size++; // <-- BOOM

C# version of PriorityQueue for compare

If you are on .NET framework 6 (or newer) you just need:

var pQ = new PriorityQueue<int, int>();

If you add items you can give them a priority(2nd parameter):

pQ.Enqueue(1, 100);
pQ.Enqueue(2, 10);
// ...

or you have a complex logic that you want to reuse, then use a custom comparer:

public class MyFancyIntComparer : IComparer<int>
{
    public int Compare(int x, int y)
    {
        // replace following with a fancy logic
        return x.CompareTo(y);
    }
}

---

var pQ = new PriorityQueue<int, int>(new MyFancyIntComparer());

---

If you are on a lower version of the .NET framework you might use(copy&paste) these internal PriorityQueues: https://referencesource.microsoft.com/#q=priorityqueue

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

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.

Priority Queue in .Net

You can use a SortedDictionary class, which is generic.

You can specify a comparer object to the constructor, which should handle the priority comparison of your objects:

public class DataComparer : IComparer<Data>
{
    public Int32 Compare(Data a, Data b)
    {
        if (a == null && b == null)
            return 0;
        if (a == null)
            return -1;
        if (b == null)
            return +1;
        return a.Priority.CompareTo(b.Priority);
    }
}

SortedDictionary<Data, Data> priQueue = new SortedDictionary<Data, Data>(
    new DataComparer());

How to get Priority of C# PriorityQueue element

I figured out that this requires usage of a try/get:

for (int i = k; i < points.Length; i++)
{
    double euclidianDistance = EuclidianDistance(points[i]);
    if (maxHeap.TryPeek(out int[] topPoint, out double priority) && euclidianDistance < priority)
    {
        maxHeap.Dequeue();
        maxHeap.Enqueue(points[i], euclidianDistance);
    }
}

---

Related Topics