Wouldn't be a good idea to use a HashSet or a Queue by priority?

The complexity of Enqueue/Dequeue would be O(1) instead of O(log n).

It would be nice if there were instructions for how to add this project to a Unity project. NuGet doesn't appear to be supported.

And then having the FastPriorityQueue be a public class inside the PriorityQueueNode?
public partial class PriorityQueueNode { public sealed class FastPriorityQueue<T> : IPriorityQueue<T> where T : PriorityQueueNode {

Then you could make all the PriorityQueue properties { get; protected set;} Won't get a speed increase, just a slight safety increase.

Also, what is the purpose of _numNodesEverEnqueued? if you went to only using _numNodes, I don't see any loss, as once the Queue is cleared, it's safe to start at zero again for insertion index, correct?

Anyway, don't mean to nitpick, I got a nice speed bump by swapping to your Queue over the generics.

` SimplePriorityQueue priorityQueue = new SimplePriorityQueue();

    //Now, let's add them all to the queue (in some arbitrary order)!
    priorityQueue.Enqueue("2 - Jason", 1516779438070);
    priorityQueue.Enqueue("1 - Joseph", 1516779438069);
    priorityQueue.Enqueue("3 - Tyler", 1516779441371); 
    
    

    //Change one of the string's priority to 2.  Since this string is already in the priority queue, we call UpdatePriority() to do this
    

    //Finally, we'll dequeue all the strings and print them out
    while(priorityQueue.Count != 0)
    {
        string nextUser = priorityQueue.Dequeue();
        Debug.Log(nextUser);
    }

`

I tried to change the numbers from example, and you dequeue them in order you queue them like normal queue, It's expected that you should dequeue them as 1, 2, 3.

I don't know it's related to the numbers being big (not support long etc). Or maybe I tried to use it wrong way. I should be able to use it with these numbers because they're timestamp values and I want to order the queue with them

Thanks

Koxel/Koxel@3ddce61#commitcomment-21388708
ugh

Overview

When working with priority queues it's often useful to be able to access the priority of the head node as you dequeue it. This is especially common in many pathfinding and graph traversal algorithms.

When using GenericPriorityQueue or FastPriorityQueue you manipulate the nodes directly and so have access to their respective Priority properties.

When using SimplePriorityQueue the nodes are not publicly exposed and so it is currently necessary to first get the priority of the head element, and only then dequeue it.

A naïve user implementation might look like this:

public static class SimplePriorityQueueExtensions
{
    public static TItem Dequeue<TItem, TPriority>(
        this SimplePriorityQueue<TItem, TPriority> queue,
        out TPriority priority)
    {
        priority = queue.GetPriority(queue.First);
        return queue.Dequeue();
    }
    
    public static bool TryDequeue<TItem, TPriority>(
        this SimplePriorityQueue<TItem, TPriority> queue,
        out TItem first, 
        out TPriority priority)
    {
        // Can't use TryDequeue because by that point we've already lost the priority value stored :(
        if (!queue.TryFirst(out first))
        {
            priority = default;
            return false;
        }
        
        priority = queue.GetPriority(first);
        queue.Dequeue(); // Already have 'first' assigned, so no need to store it again.
        return true;
    }
}

This achieves the desired result using SimplePriorityQueue.GetPriority (added as a result of related issue #27), but this implementation is suboptimal (even if for a moment we ignore the fact that it is not thread safe).

The Problem

In its current implementation SimplePriorityQueue.Dequeue() retrieves an internal SimpleNode , which contains both the Data as well as the Priority properties we need, but only returns the data to the caller:

public TItem Dequeue()
{
    lock(_queue)
    {
        if(_queue.Count <= 0)
        {
            throw new InvalidOperationException("Cannot call Dequeue() on an empty queue");
        }

        SimpleNode node =_queue.Dequeue();
        RemoveFromNodeCache(node);
        return node.Data;
    }
}

So by performing Dequeue/TryDequeue we actually already have access the priority value of the head node that we want! It's just not exposed to the caller.

They instead have to make an additional GetPriority call, which in the general case means a _itemToNodesCache lookup since it is intended to work for any node, that could be avoided altogether.

The Proposal

It would be trivial to add a Dequeue and TryDequeue overload to SimplePriorityQueue that each have a out TPriority parameter, since we get that value for free in both of the existing implementations.

For example, the overload for Dequeue could be:

/// <summary>
/// Removes the head of the queue (node with minimum priority; ties are broken by order of insertion), 
/// and returns it along with its priority.
/// If queue is empty, throws an exception
/// O(log n)
/// </summary>
public TItem Dequeue(out TPriority priority)
{
    lock(_queue)
    {
        if(_queue.Count <= 0)
        {
            throw new InvalidOperationException("Cannot call Dequeue() on an empty queue");
        }

        SimpleNode node =_queue.Dequeue();
        priority = node.Priority; // <---- added
        RemoveFromNodeCache(node);
        return node.Data;
    }
}

And the overload for TryDequeue could be:

/// <summary>
/// Removes the head of the queue (node with minimum priority; ties are broken by order of insertion), 
/// and sets it to first along with its priority.
/// Useful for multi-threading, where the queue may become empty between calls to Contains() and Dequeue()
/// or between GetProprity() and TryDequeue()
/// Returns true if successful; false if queue was empty
/// O(log n)
/// </summary>
public bool TryDequeue(out TItem first, out TPriority priority)
{
    if (_queue.Count > 0)
    {
        lock (_queue)
        {
            if (_queue.Count > 0)
            {
                SimpleNode node = _queue.Dequeue();
                first = node.Data;
                priority = node.Priority; // <---- added
                RemoveFromNodeCache(node);
                return true;
            }
        }
    }
    
    first = default(TItem);
    priority = default(TPriority); // <---- added
    return false;
}

They are identical to the existing implementations, except for assigning the priority out parameter. There should be no performance overhead other than one additional assignment, which is trivial (and would still happen with (Try)GetPriority anyway).

This would even have the additional benefit of being thread-safe, unlike the naïve user implementation provided as an example at the start.

If it was deemed necessary to keep the function names unique and not overload them they could be named DequeueWithPriority and TryDequeueWithPriority respectively, or something comparable. 2nd hardest problem in computer science and all that...

Keeping things 'Simple'

The argument could be made that if you care enough about optimizing Dequeue with priority you should just use GenericPriorityQueue or FastPriorityQueue, and that the public signature of SimplePriorityQueue should be kept, well, 'simple'.

That is valid, but given how trivial this implementation would be to add it just seems like such a missed opportunity, especially for saving an additional hash for an operation that as I understand it is very common in some of the main applications of Priority Queues.

More importantly SimplePriorityQueue promises to be thread-safe, and requiring the user to make three calls means we can no longer guarantee that the operation is thread-safe - it's now up to the user to ensure that they correctly lock access to the container for the duration of their First (or TryFirst), GetPriority and Dequeue calls. Yuck.

It just seems like the equivalent of creating a SimpleDictionary implementation that promises to be "thread-safe" , but only has Contains and GetValue and does not provide a TryGetValue:

// Needs to hash key twice
// Cannot guarantee thread-safe value access
if(SimpleDictionary.Contains(key))
{
    Value value = SimpleDictionary.GetValue(key);
    // Use value here ...
}


// Needs to hash key once
// Can guarantee thread-safe value access
if(SimpleDictionary.TryGetValue(key, out Value value))
{
    // Use value here ...
}

The primary purpose of this library is performance (it's in the name after all), so I'd like to make the argument that even its 'simple' implementation would benefit from this addition, while (especially if we use unique names) remaining backwards compatible.

The proposed addition would make a common access pattern safer (one less place the user has to worry about thread safety) and faster, at no extra cost.

Relevant issues

• #27 : The first discussion of this issue, which resulted in the addition of SimplePriorityQueue.GetPriority. As outlined here that is sub-optimal in this specific case where we already have the node and so don't need to hash to retrieve it. It also requires the caller to manage their own thread safety which the proposed change also throws in for free.

FYI - Reusing nodes (from one queue to another) breaks the debug check for QueueIndex in Contains(node).

Maybe change the QueueIndex back to zero on a Dequeue or possibly change to 0 in debug check before Contains?

EDIT: Sorry - this is for FastPriorityQueue

The NuGet package installs without issue when running the app, however, the following exception is thrown: Could not load file or assembly 'Priority Queue UWP, Version=4.0.3.0, Culture=neutral, PublicKeyToken=null'. The system cannot find the file specified.

Looking in the output directly there is a "Priority Queue.dll", which matches the contents of the package.

I think the fault is in the nuspec file, line 26: <file src="..\Priority Queue UWP\bin\Release\netcore45\Priority Queue UWP.dll" target="lib\netstandard1.0\Priority Queue.dll" />

The src matches the name of the assembly that is being looked for. Unfortunately, I'm not exactly sure what root cause is.

For using SimplePriorityQueue...As far as I can tell from the implemented constraint, where TPriority : IComparable<TPriority>,
this is based on the fact that some constructors use Comparer<TPriority>.Default
but what if I have only intend to use IComparer (instead of IComparable) and the TPriority object cannot inherit from IComparable<>?
for example, I want to write something like: var priorityQueue = new SimplePriorityQueue<int, Vertex>(new VertexSorter());
where VertexSorter inherits from IComparer<Vertex>', and not change the class Vertexto inherit fromIComparable`.

I'm not sure that the implementation can have it both ways, but I thought I'd pose the question to you. Otherwise, my options are to write a small wrapper class for Vertex or try to remove the restriction from a local version of your awesome library.

I see that there is a _numNodesEverEnqueued field in the class.

When you have a single queue for the lifetime of your application being used, sooner or later the bits for that Int64 will flip, resulting in now incorrect "aging" of future entries.

Imagine the following scenario:

Before the field overflows, we had the following items in the queue:

Now, if we were to add an element with a priority of 1 and value 5, we get incorrect behavior. The queue is no longer stable, in that 3, 9, 5 will not be dequeued in that order, but rather 5, 3, 9.

As a side effect, this effectively means that 3 and 9 (ALL the items left in the queue when the bit shifts) in applications with extreme throughput will be blocked from ever being dequeued if a priority of 1 is the main player in the queue.

Should be able to get a big speed gain in GenericPriorityQueue if number comparison JITs into a single CMP instruction (the current method using Comparison<TPriority> does not).

In fact if that works, I might be able to move the generics over to FastPriorityQueue and get rid of GenericPriorityQueue altogether.

For example:
priorityQueue.Enqueue("4 - Joseph", 4);
priorityQueue.Enqueue("2 - Tyler", 0);
priorityQueue.Enqueue("1 - Jason", 1);
priorityQueue.Enqueue("4 - Ryan", 4);
priorityQueue.Enqueue("3 - Valerie", 3);

//the output:
//1 - Jason
//2 - Tyler
//3 - Valerie
//4 - Joseph
//4 - Ryan

But I want the order is reverse order
//4
//3
//2
//1.

Does anyone know?

I'm pretty sure I'm not currently doing this. I should be.

See http://stackoverflow.com/questions/5205738/how-do-you-include-xml-docs-for-a-class-library-in-a-nuget-package

The name of dll assembly "Priority Queue.dll" causes issues on systems that do not allow spaces in file names. I would like to use this project in my work but cannot due to this limitation. I request that you update the nuget package to change the assembly name to PriorityQueue.dll or similar (without a space) to overcome this. Thank you.

I've been finding in my project that I need multiple priority queues for different purposes, and some of the same objects need to go in each queue. This obviously requires multiple index values, and potentially multiple priority values, but FastQueuePriorityNode only allows for one of each.

At first I handled this by making a renamed copy of FastPriorityQueue and its node class, converting the node classes to interfaces, implementing both interfaces on the queued object, and using the copy for the second queue. But now "two queues" has expanded to "arbitrarily many queues" and that won't work any more.

SimplePriorityQueue can handle this by wrapping the object in a per-queue node wrapper, but I'd rather not accept the performance cost for that.

I'm working on a solution for my project, but I'm not sure it won't have any project-specific details and I expect there are plenty of other people who would find multi-queue support useful.

I have an event driven model in which each event is assigned with a timestamp in DateTime type, and smaller timestamp should dequeue first. There is data loss when converting long DateTime.Ticks to float priority. I understand in most cases float type is enough for priority, but in some cases it will cause trouble. How about leave the pritority comparison to user? This is the common pattern in most collections in .NET world.

public interface IPriorityQueue<T, P> : IEnumerable<T>
{
    void Enqueue(T node, P priority);
    ...
}

public sealed class SimplePriorityQueue<T, P> : IPriorityQueue<T, P>
{
    public SimplePriorityQueue( Comparer<P> comparer = Comparer<P>.Default )
    {
        ...
    }
}

Hi, is there any specific reason why FastPriorityQueueNode.cs is a class and not an interface? Should be something like IFastPriorityQueueable

Hello, can you please upgrade the project to .NET Standard Class Library? It will become easy to use&integrate.

Thank you very much :)

Hey, I was just looking at your code here and noticed that you didn't check insertionIndex for wrap-around cases in the HasHigherPriority function. It's probably not noticeable, but if one PriorityQueue was used for a long time, it could potentially cause issues there. But then again, it is kind of a rare case, so I don't know if it's worth it to do the proper checks every time.

Just thought I'd let you know.

if node has same prioirty, enqueue has keep seq by inser timing? can you show the prove?

From comments here: see if struct performs better due to cache coherence.

The code to keep the priority queue stable is not necessary for most applications. Separating that code out into a separate class would make the implementation faster.

Hello BlueRaja,

I just tried your Priority Queue and the Enqueue time is pretty good.
But when i try to use Dequeue i get horrible performance results.
(Dequeue is also slow when using FastPriorityQueue)

// Generating 1_000_000 Random Ints
var randomInts = WordHelper.GenerateRandomInts(
    1_000_000, int.MinValue + 5, int.MaxValue - 5);

var simpleQ = new SimplePriorityQueue<int, int>();

// Enqueue total time around 700-800 ms, pretty fine
foreach (var item in randomInts)
{
    simpleQ.Enqueue(item, item);
}

var dequeueList = new List<int>(randomInts.Length);

// The Dequeue time is so slow that its not usable, takes minutes...
while (simpleQ.Count > 0)
{
    if (simpleQ.Count % 100 == 0)
    {
        Debug.WriteLine($"items left {simpleQ.Count}");
    }

    dequeueList.Add(simpleQ.Dequeue());
}


// Helper func to generate random ints
public static int[] GenerateRandomInts
         (int numInts, int min, int maxIncl)
{

    var ret = new int[numInts];
    var rnd = new Random();

    for (int i = 0; i < numInts; i++)
    {
        ret[i] = (rnd.Next(min, maxIncl + 1));
    }

    return ret;
}

Edit:
I tried the PriorityQueue from Microsoft
https://github.com/dotnet/runtime/blob/main/src/libraries/System.Collections/src/System/Collections/Generic/PriorityQueue.cs

And it has good Enqueue and Dequeue performance.
Maybe you can compare these to find out whats wrong.

Am i doing something wrong?
I tried other Priority Queues i found online and the Dequeue time for 1M elements takes less than a second.

Best Regards

Charles

@BlueRaja is it much effort to make you NuGet package compatible with the UWP? I have considered forking your source and taking what I need to make my project work but I figured that might be duplicate effort if this might have already been on your horizon. Just thought I would ask, thanks for your ##time!

In Christ,
Rock

For my use case, I'll have an unknown number of queues processing at the same time and in quick succession. It would be ideal if I could use ArrayPool to pool array allocations and then initialize FastPriorityQueue using the pool sourced array.

Hello,

Does the queues thread safe ?

Thanks

When porting a Windows 8.1 Universal app to Windows 10 UWP, we suddenly started getting File not found exceptions for classes using the priority queue. I tested it in isolation, creating a new project, referencing the latest PriorityQueue library (4.0.0) obtained through NuGet, and we still get the same.

Here are some details:

When does this happen
During run time, whenever a priority queue object is instanciated. Otherwize, the project builds just fine.

What happens

A file not found exception is thrown, here is the complete message:

An exception of type 'System.IO.FileNotFoundException' occurred in TestApp.exe but was not handled in user code

Additional information: Could not load file or assembly 'Priority Queue UWP, Version=3.0.0.0, Culture=neutral, PublicKeyToken=null' or one of its dependencies. The system cannot find the file specified.

How is the code used.

Just a simple initializer will do, see this sample:
TestPage.txt

Additional info
For Windows 10 UWP, the following target platforms and minimum versions were specified during project creation.

I cannot think of a reason for this to happen, all the files are safely where they should be, although with windows 10 projects, all NuGet packages are stored on disk under C:/{UserName}/.nuget/packages. All files are present.

ints are nearly always faster than floats. Given how popular this library has become, and how many people are using it for non-pathfinding applications, it would be nice to have another queue that supports int for people who don't need float

Please add support for BlockingCollection.
BlockingCollection is very useful in multi-threaded code since it allows you to do something like this:

while(running) { 
    var next = queue.Take();
 }

Thanks.

I had to replace the existing NUnit nuget package with the NUnitTestAdapter.WithFramework buget package to run the tests in the Debug configuration

as described in the following Visual Studio Develop Community thread

https://developercommunity.visualstudio.com/content/problem/527276/nunit-2-unit-tests-not-running-in-vs-2019.html

the test do run in the Release configuration with the existing package.

SimplePriorityQueue internally creates a Dictionary<TItem, IList<SimplePriorityQueue<TItem, TPriority>.SimpleNode>> mapping items to queue nodes. But when TItem is a struct that doesn't implement IEquatable<T>, like System.Drawing.PointF or Unity's Vector3, accessing the dictionary is slow, because the default equality comparer does boxing conversions to call inherited methods. (More discussion on Stack Overflow.)

The usual solutions are to implement IEquatable<T> on all structs, which isn't an option for third party types (e.g. Unity deliberately doesn't implement it), or pass a custom IEqualityComparer<T> to the dictionary constructor, which isn't an option here since it's constructed internally. Instead, one must use a wrapper type or switch to FastPriorityQueue.

SimplePriorityQueue should add a constructor that takes an IEqualityComparer<TItem> and passes it to the dictionary, and/or warn users that TItem should only be a value type if it implements IEquatable.

I give you one case

        [Test]
        public void TestEveryDequeued()
        {
            TQueue queue2 = CreateQueue();
            var node1 = new Node(1);
            var node2 = new Node(1);
            var node3 = new Node(1);

            queue2.Enqueue(node1, 1);
            queue2.Enqueue(node2, 1);
            queue2.Enqueue(node3, 1);

            var dequeuedNodes = new List<Node>();

            for (var i = 0; i < 1000; i++)
            {
                dequeuedNodes.Add(queue2.Dequeue());
                queue2.Enqueue(new Node(1), 1);
            }

            Assert.Contains(node1, dequeuedNodes);
            Assert.Contains(node2, dequeuedNodes);
            Assert.Contains(node3, dequeuedNodes);
        }

Second assertion will failed with any number of iterations

My first debug was on paper by code :)

You can see what happenes

Currently, the NuGet package for this project targets .NET Standard 1.0, as well as a a coulple other .NET framework targets:

I propose that, in addition to the current target platforms, other .NET targets that implement .NET Standard 1.0, including .NET Standard 2.0, .NET Core 3.1, .NET 5, etc be added explicitly as targets.

Although targeting .NET Standard 1.0 allows the project to be used on any target implementing .NET Standard, targeting the runtimes specifically can, under some circumstances, enable the compiler to apply optimizations that only work for the particular version of .NET being targeted; which may ultimately result in better performance on those platforms even with no actual code modifications. I have not profiled this myself, however; I'm simply leaning on experiences I've had with other libraries.

When the PQ is full it would be useful to add a new item and have it throw away the lowest priority item

This feature is useful in a* to have an open set of fixed size, while maintaining just the best N nodes.

The throwing away of the least priority item is the default behaviour I usually see in PQ implementations.

I admit I have only looked at the Fast PQ

This implementation of the priority queue wouldn't work well with objects in external libraries. It will also stain business objects with data-structure-related methods and properties.

If I want to put an object in this queue, it has to inherit from PriorityQueueNode. This makes any objects I want to put in the queue very tightly coupled with the queue data structure. There is definitely a way to do this and get the same performance without that extreme coupling.

Hello,
I wanted to use the priority queue in a PCL (Portable Class Library).
But it is not working. I tried to create a nuget package but that failed.

It is easy to create a PCL from the code and if I compile it an directly reference the lib it works. But i failed to create a nuget-package..

Cheers

I believe a smaller value like float would increase performance. Try it out and see if it does.

Background:

I have been evaluating this priority queue to manage the processing of a large collection of documents that my program will receive. These come from 2 sources:

1. from a web service API call from automation
2. from a user in another program

At the head of the queue, I have a set of "processors" that operate upon the document (the number of threads are based on the desired server load / processing velocity tradeoff user wants).

I would like the user (point 2 above) to be able to "push in" with their document. My problem though is that the web service automation may have submitted details that are a pre-requisite processing to the user's document, so I have occasions where I need to escalate the priority of already queued items.

On the surface this is pretty straight forward with SimplePriorityQueue

Have a dictionary of Item by id and call UpdatePriority on it first before enqueuing the user submitted document. (I have other mechanisms in place to ensure that two documents for the same id don't get allocated to different "processors"

Issue:
Unless I have missed something, there is no way that I can see for a consumer that dequeues to know whether it is safe to do so. In a multi threaded environment, even if I check count > 0, another thread may call Dequeue before me. Similarly, if I want to call UpdatePriority, there is a race condition between me calling Contains, receiving true and then UpdatePriority because _queue is unlocked (briefly).

Is it possible to use the Try... convention (like ConcurrentDictionary etc)

For example:
public bool TryUpdatePriority(TItem item, TPriority priority)
public bool TryRemove(TItem item)
public bool TryDequeue(out TItem item)

It feels a bit dirty (and inefficient) to be capturing and swallowing InvalidOperationExceptions

A simple addition which lets people prioritize maximum elements over minimum ones. It also nicely decouples the default comparer of the priority class from the one used in the queue.

One of the features states : Has a stable priority queue implementation (ie. if two items are enqueued with the same priority, they'll be dequeued in the same order they were enqueued)

However, the below code fails this feature test, please can you fix. Thanks

class Program
{
    private const int MAX_QUEUE_LENGTH = 10000;

    static void Main(string[] args)
    {
        FastPriorityQueue<GeocodingRequest> priorityQueue = new FastPriorityQueue<GeocodingRequest>(MAX_QUEUE_LENGTH);

        // HIGH PRIORITY REQUESTS
        var highReq1 = new GeocodingRequest("HIGH 1", 1, "{ }");
        var highReq2 = new GeocodingRequest("HIGH 2", 2, "{ }");
        var highReq3 = new GeocodingRequest("HIGH 3", 1, "{ }");
        var highReq4 = new GeocodingRequest("HIGH 4", 2, "{ }");

        // LOW PRIORITY REQUESTS
        var lowReq1 = new GeocodingRequest("LOW 1", 1, "{ }");
        var lowReq2 = new GeocodingRequest("LOW 2", 2, "{ }");
        var lowReq3 = new GeocodingRequest("LOW 3", 1, "{ }");
        var lowReq4 = new GeocodingRequest("LOW 4", 2, "{ }");

        // ENQUEUE REQUESTS
        priorityQueue.Enqueue(lowReq1, (int)Priority.Low);
        priorityQueue.Enqueue(lowReq2, (int)Priority.Low);
        priorityQueue.Enqueue(highReq1, (int)Priority.High);
        priorityQueue.Enqueue(highReq2, (int)Priority.High);
        priorityQueue.Enqueue(highReq3, (int)Priority.High);
        priorityQueue.Enqueue(highReq4, (int)Priority.High);
        priorityQueue.Enqueue(lowReq3, (int)Priority.Low);
        priorityQueue.Enqueue(lowReq4, (int)Priority.Low);

        while (priorityQueue.Count != 0)
        {
            var nextGeocodingRequest = priorityQueue.Dequeue();
            Console.WriteLine(nextGeocodingRequest.Tag);
        }

        // OUTPUT is actually as below       But should be as below
        // HIGH 4                            HIGH 1
        // HIGH 2                            HIGH 2
        // HIGH 1                            HIGH 3
        // HIGH 3                            HIGH 4
        // LOW 1                             LOW 1
        // LOW 4                             LOW 2
        // LOW 2                             LOW 3
        // LOW 3                             LOW 4

        Console.ReadLine();
    }
}

public class GeocodingRequest : FastPriorityQueueNode
{
    public string Tag { get; set; }
    public int Batch { get; set; }
    public string Payload { get; set; }
    public GeocodingRequest(string tag, int batch, string payload)
    {
        Tag = tag;
        Batch = batch;
        Payload = payload;
    }
}

public enum Priority
{
    Unknown = 0,
    High = 1,
    Medium = 2,
    Low = 3,
}

Just cloned this project. The last commit says "Removed Priority Queue csharp code and replaced by compiled DLL;" but the said dll file is not found in Assets/DLLs. Maybe it wasn't pushed.

It appears that the documentation of FastPriorityQueueNode.Priority is from some previous version as it talks about setting the Priority in the constructor of the node, and yet FastPriorityQueue.Enqueue now has the priority as a parameter, so it seems wrong for the node to be setting anything, and sure enough, the example doesn't.

Is it the example or the Priority documentation that is misleading?

Could you please add string name to this assembly? I cannot reference it in my project that is strongly named.

First I get this warning on compile time:

CS8002	Referenced assembly 'Priority Queue, Version=4.2.0.0, Culture=neutral, PublicKeyToken=null' does not have a strong name.

And than this error on runtime:

System.IO.FileLoadException: Could not load file or assembly 'Priority Queue, Version=4.2.0.0, Culture=neutral, PublicKeyToken=null' or one of its dependencies. A strongly-named assembly is required. (Exception from HRESULT: 0x80131044)

Sometimes you only want the top N results, in this case it makes sense to implement an a method to remove the lowest priority N results.

Currently the only way to do this is to build a new Queue. i.e

                if (_collection.Count > 1024)
                {
                    var c = new FastPriorityQueue<PrioOccurancePossibility>(2048);
                    foreach(var cc in _collection.Take(1024)) c.Enqueue(cc, cc.Priority);
                    _collection = c;
                }

Just a little Typo in the Description of GenericPriorityQueue,
/// <typeparam name="TItem">The values in the queue. Must extend the GenericPriorityQueue class</typeparam>
It shoud be
/// <typeparam name="TItem">The values in the queue. Must extend the GenericPriorityQueueNode class</typeparam>

Thanks for the Great Work!

Sometimes the priority is a part of information. It would be nice to have overloaded First element lookup and Dequeue which let the user to retrieve it.

Hello,

I was hoping to use this in a project I'm working on. But it seems it doesn't support dotnetcore, which is surprising as I can't see any particular reason the code wouldn't work in .NET Core.

error: Package OptimizedPriorityQueue 4.0.0 is not compatible with netcoreapp1.0 (.NETCoreApp,Version=v1.0). Package OptimizedPriorityQueue 4.0.0 supports:
error: - net20 (.NETFramework,Version=v2.0)
error: - net45 (.NETFramework,Version=v4.5)
error: - netcore45 (.NETCore,Version=v4.5)
error: One or more packages are incompatible with .NETCoreApp,Version=v1.0.

Would you recommend I make a wrapper for FastPriorityQueue for use with value types or to use the SimplePriorityQueue for maximum performance? As long as there not too many of them, 2D grid points could be hashed to an integer, but with a wrapper, there will definitely be some overhead. I saw some discussion of this in the closed issue, but I am guessing that was before the SimplePriorityQueue was implemented.

There are too many queues sharing primarily the same code. Using generics is not an option because priority-comparison turns out to be too slow. I should look into Text Templates for code generation to reduce the code redundancy.

It seems to me that the nodes are just data files. As such, it might be possible to use structs, which could use less memory and possibly be faster. My first blush look at it says it could work, but you have a better testing setup than I do.

Side node, thanks for this awesome library, it's the best PriorityQueue I've found for C#!