C# Reference ยท Collections
The PriorityQueue<TElement,TPriority> class
Reference for C# PriorityQueue<TElement,TPriority>: Enqueue, Dequeue, Peek, TryDequeue, custom comparers, ordering of equal priorities and complexity.
PriorityQueue<TElement, TPriority> (namespace System.Collections.Generic, added in .NET 6) is a collection that always hands out the element with the smallest priority value first. You add items together with a priority, and Dequeue removes the one that is currently most urgent. It is built on a binary min-heap stored in an array, so adding and removing are both O(log n).
The element and the priority are separate values: the queue never looks at the element itself. That makes it easy to use with strings, records or anything else. There is no thread-safe version in the framework, and you cannot enumerate it in priority order.
var queue = new PriorityQueue<string, int>(); queue.Enqueue("write report", 2); queue.Enqueue("fix outage", 1); string next = queue.Dequeue(); // "fix outage"
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with Console.ReadLine()), it gets the next line from this box.
Syntax
public class PriorityQueue<TElement, TPriority> { public PriorityQueue(); public PriorityQueue(int initialCapacity); public PriorityQueue(IComparer<TPriority>? comparer); public PriorityQueue(IEnumerable<(TElement Element, TPriority Priority)> items); public int Count { get; } public IComparer<TPriority> Comparer { get; } public UnorderedItemsCollection UnorderedItems { get; } public void Enqueue(TElement element, TPriority priority); public TElement Dequeue(); public bool TryDequeue(out TElement element, out TPriority priority); public TElement Peek(); public bool TryPeek(out TElement element, out TPriority priority); public TElement EnqueueDequeue(TElement element, TPriority priority); public void EnqueueRange(IEnumerable<(TElement, TPriority)> items); public void EnqueueRange(IEnumerable<TElement> elements, TPriority priority); public void Clear(); public int EnsureCapacity(int capacity); public void TrimExcess(); }
| Name | Description |
|---|---|
element |
The value to store. It is never compared. |
priority |
The sort key. The smallest value (by the comparer) leaves first. |
comparer |
Optional IComparer<TPriority>. Pass a reversed comparer for a max-heap. |
items |
Initial (element, priority) pairs. The heap is built in O(n). |
Count |
Number of items. |
Returns: Dequeue and Peek return the element with the smallest priority. TryDequeue and TryPeek return false (and default values) when the queue is empty.
Errors: Dequeue and Peek throw InvalidOperationException on an empty queue. Priorities must be comparable: if TPriority has no default ordering and no comparer is given, an exception is thrown when the queue first needs to compare two values.
Usage notes
- Smallest first. For "largest first", pass
Comparer<int>.Create((a, b) => b.CompareTo(a))or enqueue the negated priority (careful withint.MinValue). - Equal priorities are not stable. Two items with the same priority can come out in either order. If insertion order must be kept, use a tuple priority such as
(priority, sequenceNumber). - Priority is fixed at enqueue time. There is no "change priority" method and no way to remove a specific element. The usual workaround is to enqueue a new entry and ignore the old one when it comes out ("lazy deletion"), which Dijkstra-style algorithms use.
- No ordered enumeration.
UnorderedItemslists the contents in internal heap order. To read in priority order you must dequeue. - Complexity:
EnqueueandDequeueare O(log n),Peekis O(1), building from a collection is O(n).EnqueueDequeueis cheaper than separate calls when you push and pop together. - Not thread-safe. Guard it with a
lock, or use aChannelwith a single consumer. - Availability. .NET 6 or later; it does not exist in .NET Framework.