For a game I am working on, I need to perform some pathfinding on top of a graph. The graph contains edges with a weight to allow us to pick the “best” path that reflects a cost to use each path, rather than merely the smallest number of nodes.

I’m using Dijkstra’s Algorithm which requires among other things a queue that is sorted by priority.

The game is being built in Unity, which uses C# as it’s preferred programming language. C# has a Queue<T>, and it has SortedList<T> and other structures by default that look useful, but have various limitations, and this has annoyed me a great deal.

Queue<T> is strictly FIFO, you can Queue<T>.Enqueue() something to the end, and Queue<T>.Dequeue() the head of the queue. And you can peek into the queue etc. The only way to insert mid-queue is convert to a List<T> or an array and manipulate it, then re-create the queue from that list/array. That sucks.

SortedList<T> is great, you can insert something into the list and it’ll be automatically sorted, presuming you have an IComparable interface on whatever type you’re using. But SortedList<T> doesn’t accept duplicate keys, so if you have two edges in your graph with equal weight it dies.

Okay, so we could just use a plain List<T> and do the sorting ourselves. And that’s fine, but if we’re doing that we take a penalty to insert into the middle of List<T> because under the hood it really resizes the array. Which is more of a hit than we need to take - the queue will be adjusted constantly while walking the graph.

C# doesn’t have PriorityQueue<T>, even though it’s clearly a useful structure to have (based on the number of implementations around!). It seems to be stuck in limbo in tickets on GitHub about what corner cases it would trip up on based on how someone expects to use it. Okay, fine, we pick one.

Like I said, there’s a bunch of implementations. Some impose rules about what type is used to sort the queue, most are probably more than I need. But I also wanted to learn a bit more about C# so why not write something myself. So, here it is .. a PriorityQueue that might work okay and definitely isn’t optimised.

This uses LinkedList<T> internally. Enqueue is O(n) because we have to walk the linked list to find a place to insert. However, the insert into the list itself is O(1) due to it being a linked list. It is a stable queue, in that the order of enqueue is respected (effectively, equal priority items behave like a FIFO). Dequeue is O(1) since it’s just the head.

I have no view on whether the “right” enqueue/dequeue costs should be O(n) and O(1) respectively, but there’s probably not much overall gain in shifting it around to try to make enqueue cheaper at the expense of dequeue.

You can use any type with IComparable hooks as the sort key. I’m using it with int but if you had some reason to do it with string or MyCrazyType then it should work fine.

Implemnentation follows. It probably needs IEnumerable support at some point to allow LINQ support, but I don’t currently need it.

using System.Collections.Generic;
using System;

namespace DataStructures.Queue {
	public class PriorityQueueEntry<TPrio,TItem> {
		public TPrio p { get; }
		public TItem data { get; }
		public PriorityQueueEntry(TPrio p, TItem data) {
			this.p = p;
			this.data = data;
		}
	}

	public class PriorityQueue<TPrio,TItem> where IPrio : IComparable {
		private LinkedList<PriorityQueueEntry<TPrio,TItem>> q;

		public PriorityQueue() {
			q = new LinkedList<PriorityQueueEntry<TPrio,TItem>>();
		}

		public int Count { get { return q.Count(); } }

		public void Enqueue(TPrio p, TItem data) {
			if (q.Count == 0) {
				q.AddFirst(new PriorityQueueEntry<TPrio,TItem>(p,data));
				return;
			}
			// This is a bit classical C but whatever
			LinkedListNode<PriorityQueueEntry<TPrio,TItem>> current = q.First;
			while (current != null) {
				if (current.Value.p.CompareTo(p) > 0) {
					q.AddBefore(current,new PriorityQueueEntry<TPrio,TItem>(p,data));
					return;
				}
				current = current.Next;
			}
			q.AddLast(new PriorityQueueEntry<TPrio,TItem>(p,data));
		}

		public TItem Dequeue() {
			// LinkedList -> LinkedListNode -> PriorityQueueEntry -> data
			var ret = q.First.Value.data;
			q.RemoveFirst();
			return ret;
		}
	}
}