Update 2: I have created a PriorityQueue that only sorts when the indexed value changes here
Update: I will be creating a new version of this that determines whether sorting is actually required before sorting (i.e. whether any of the sort keys have changed).
I was looking for a priority queue in C# for some pathing algorithms. The built in SortedDictionary doesn't allow duplicate keys and I wanted a collection that didn't require me to remove and re-add an item to update it. There were a lot of good solutions on the internet but I think I came up with a really simple and clever implementation.
I realised, for me, the only time I access an item is by popping/dequeueing it so I only really need to sort the collection immediately before popping it. Doing it this way means I don't need to worry about inserting an item at the correct point or updating the collection when the values inside it change. I checked to see what algorithm a List(T).Sort uses on MSDN and was really happy to find the following:
This method uses the Array.Sort method, which applies the introspective sort as follows:
This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal. On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n ^ 2) operation.
- If the partition size is fewer than 16 elements, it uses an insertion sort algorithm.
- If the number of partitions exceeds 2 * LogN, where N is the range of the input array, it uses a Heapsort algorithm.
- Otherwise, it uses a Quicksort algorithm.
The constructor accepts an optional IComparer<T> to decide how items are compared.
The big weakness in this solution is it sorts each time you pop so there is a big overhead if you do sequential pops without the sort key ever having changed. The trade off is we don't need to worry about updating the collection each time a sort key is updated. This is handy if the sort key is being tracked and updated regularly from somewhere else.