Priority queue implementations in C#
- Three default implementations of the priority queue data structure
- Easy to use with a custom comparer
- Easy way to create your own implementation by implementing the
IPriorityQueueinterface
Install-Package PriorityQueues
More info: nuget package
First we'll define a sample class that which will be used in our queue.
class Element { public string Name { get; set; } public float Priority { get; set; } }
Then we can create a new priority queue using one of the implementations, and pass in a comparer
// Create a new instance of BinaryPriorityQueue IPriorityQueue<Element> myPriorityQueue = new BinaryPriorityQueue<Element>((a, b) => a.Priority.CompareTo(b.Priority)); // this will produce a min-heap, use b.Priority.CompareTo(a.Priority) for a max-heap // Insert some elements myPriorityQueue.Enqueue(new Element { Priority = 5, Name = "A" }); myPriorityQueue.Enqueue(new Element { Priority = 7, Name = "B" }); myPriorityQueue.Enqueue(new Element { Priority = 4, Name = "C" }); // Get the top element (one with the highest priority value) and remove it myPriorityQueue.Dequeue(); // Name: "B", Priority: 7 // Get the top element's value without removing it myPriorityQueue.Peek(); // Name: "A", Priority: 5; // Get the top element again, this time it will be removed myPriorityQueue.Dequeue(); // Name: "A", Priority: 5 // Clear all remaining elements myPriorityQueue.Clear(); myPriorityQueue.IsEmpty(); // true
For more information on usage, check the Tests project.
There are three default implementations. BinaryPriorityQueue and MappedBinaryPriorityQueue both use a binary heap as their underyling data structure, but the latter also stores all elements in a dictionary for faster lookup and element removal at the expense of slight memory and computational overhead. FibonacciPriorityQueue uses a fibonacci heap for faster amortized enqueueing and dequeueing times.
| Operation | BinaryPriorityQueue | MappedBinaryPriorityQueue | FibonacciPriorityQueue |
|---|---|---|---|
| Peek | O(1) | O(1) | O(1) |
| Enqueue | O(log n) | O(log n) | Θ(1) |
| Dequeue | O(log n) | O(log n) | Θ(1) |
| IsEmpty | O(1) | O(1) | O(1) |
| Remove | O(log n) | O(log n) | O(n) |
| Contains | O(n) | O(1) | O(n) |
| Clear | O(n) | O(n) | O(1) |
| DecreaseKey | N/A | N/A | Θ(1) |
Θ - amortized time
Inspired by WilliamFiset's playlist explaining how priority queues work, along with sample implementation code
Fibonacci heap implementation based on Gabor Makrai's Java implementation