Clone wiki

High Speed Priority Queue for C# / Getting Started

Adding the Priority Queue to your project

  1. Add Priority Queue/Priority Queue.csproj to your solution.

  2. Reference the Priority Queue project from any projects you want to use it from.

  3. Add using Priority_Queue to the top of any files you want to use it from.

Using the Priority Queue

In order to use HeapPriorityQueue, the class you want to enqueue must extend the PriorityQueueNode class (Why?).

//Example of how to create a priority queue node class
public class MyNode : PriorityQueueNode
     //Put custom properties here

To actually create the priority queue, you need to pass the max queue-size to its constructor.

HeapPriorityQueue queue = new HeapPriorityQueue(MAX_SIZE);

This is the maximum number of nodes you will ever enqueue. For speed purposes, the queue does not attempt to resize itself; enqueuing more than the max number of nodes will cause an exception to be thrown.

Note that it is recommended - though not required - that you access the queue through its concrete type, HeapPriorityQueue, rather than its interface IPriorityQueue, because the JIT can theoretically optimize method calls on concrete types better.

After that, calls to Enqueue(), Dequeue(), Contains() etc. are straight-forward.

MyNode myNode = new MyNode();
double priority = 10;
queue.Enqueue(myNode, priority);
//Later ...
MyNode nextNode = queue.Dequeue();

If you need to update the priority of a node, call queue.UpdatePriority(node, priority). Remember, do not alter any of the properties from the PriorityQueueNode base-class yourself!

queue.UpdatePriority(nodeAlreadyInQueue, 100);


Be careful not to call UpdatePriority() on nodes that aren't in the priority queue, or to call Enqueue() on nodes that are. Also make sure not to add the same node to two different priority queues at once.

Also note that the priority queue is not thread safe.

Here is a fully working minimal example


using System;
using Priority_Queue;

namespace Priority_Queue_Example
    class Program
        //The class to be enqueued.
        public class User : PriorityQueueNode
            public string Name { get; private set; }
            public User(string name)
                Name = name;

        private const int MAX_USERS_IN_QUEUE = 10;

        static void Main(string[] args)
            //First, we create the priority queue.  We'll specify a max of 10 users in the queue
            HeapPriorityQueue<User> priorityQueue = new HeapPriorityQueue<User>(MAX_USERS_IN_QUEUE);

            //Next, we'll create 5 users to enqueue (the priority is set in the constructor)
            User user1 = new User("1 - Jason");
            User user2 = new User("2 - Tyler");
            User user3 = new User("3 - Valerie");
            User user4 = new User("4 - Joseph");
            User user42 = new User("4 - Ryan");

            //Now, let's add them all to the queue (in some arbitrary order)!
            priorityQueue.Enqueue(user4, 4);
            priorityQueue.Enqueue(user2, 0); //Note: Priority = 0 right now!
            priorityQueue.Enqueue(user1, 1);
            priorityQueue.Enqueue(user42, 4);
            priorityQueue.Enqueue(user3, 3);

            //Change user2's priority to 2.  Since user2 is already in the priority queue, we call UpdatePriority() to do this
            priorityQueue.UpdatePriority(user2, 2);

            //Finally, we'll dequeue all the users and print out their names
            while(priorityQueue.Count != 0)
                User nextUser = priorityQueue.Dequeue();

            //1 - Jason
            //2 - Tyler
            //3 - Valerie
            //4 - Joseph
            //4 - Ryan

            //Notice that when two users with the same priority were enqueued, they were dequeued in the same order that they were enqueued.