Clone wiki

High Speed Priority Queue for C# / Why do I have to implement `IPriorityQueueNode` to enqueue something?

Typical data structures will have you add (or remove, etc) items like this:

myDataStructure.Add(myValue, priority);

Internally, the Add() method might look something like this:

public void Add(T myValue, double priority)
    Node node = new Node()
        Value = myValue,
        Priority = priority

This paradigm is convenient - it allows T to be any class - but slow. Every time you call .Add(), you have to do another allocation. Allocations are fast (on Windows at least - they're pretty slow on Xbox), but not allocating is much faster (You could solve this with a pool of objects, but it would still be slower than not having to pool at all).

Additionally, to implement .Contains(), either we have to look up the value in the data structure (slow) or store a separate Dictionary<T, Node> to map values to nodes.

By forcing the values to implement IPriorityQueueNode, we can avoid both of those issues. For example, here is the for .Contains() in HeapPriorityQueue:

public bool Contains(T node)
    return (_nodes[node.QueueIndex] == node);

That lookup is about 5-10x faster than using a Dictionary<T, node>. Normally, 5-10x faster than "practically nothing" would not be a big deal; however, since IPriorityQueue.Contains() is the most-called method in many path-finding algorithms, it becomes a big deal.