.NET 6 added a long-missing collection to the base class library: PriorityQueue<TElement, TPriority>.
A priority queue is useful when you do not want to process items in the order they were inserted, but in the order of their priority. Typical examples include job scheduling, pathfinding, graph algorithms, simulations, message processing, and algorithms that need to keep only the best k elements from a much larger input.
Before .NET 6, C# developers often had to implement their own heap, use SortedSet<T>, use SortedDictionary<TKey, TValue>, or pull in a third-party package. With .NET 6, a priority queue is available directly in System.Collections.Generic.
using System.Collections.Generic;
PriorityQueue<string, int> queue = new();
queue.Enqueue("Write documentation", 3);
queue.Enqueue("Fix production issue", 1);
queue.Enqueue("Refactor helper class", 5);
while (queue.TryDequeue(out string? item, out int priority))
{
Console.WriteLine($"{priority}: {item}");
}
Output:
1: Fix production issue
3: Write documentation
5: Refactor helper class
The most important detail is this: the .NET priority queue is a min-priority queue. The item with the lowest priority value is returned first.
That is different from how people often speak about “high priority” tasks in everyday language. In .NET, if you use integers as priorities, 1 comes before 10.
What problem does a priority queue solve?
A normal Queue<T> is first-in, first-out:
A, B, C -> A is processed first
A PriorityQueue<TElement, TPriority> is priority-based:
A priority 3
B priority 1
C priority 2
B is processed first
The insertion order is not the main rule. The priority is.
This makes a priority queue ideal when the next item to process is not simply the oldest item, but the most urgent, cheapest, closest, smallest, earliest, or otherwise highest-ranked item according to your algorithm.
Common examples include:
- processing urgent jobs before normal jobs;
- always expanding the cheapest node in Dijkstra’s shortest path algorithm;
- keeping the next scheduled event in a simulation;
- finding the top
kvalues without sorting an entire collection; - merging multiple sorted streams;
- implementing simple schedulers.
The two generic types
The type has two generic parameters:
PriorityQueue<TElement, TPriority>
TElement is the value you want to store.
TPriority is the value used to decide the dequeue order.
For example:
PriorityQueue<string, int> queue = new();
Here, the element is a string, and the priority is an int.
The element and the priority can be the same type:
PriorityQueue<int, int> numbers = new();
But they do not have to be. You can store an object and use one of its properties as the priority:
public sealed class WorkItem
{
public required string Title { get; init; }
public required int Severity { get; init; }
}
PriorityQueue<WorkItem, int> queue = new();
queue.Enqueue(new WorkItem { Title = "Update logs", Severity = 4 }, priority: 4);
queue.Enqueue(new WorkItem { Title = "Fix payment outage", Severity = 1 }, priority: 1);
queue.Enqueue(new WorkItem { Title = "Clean temporary files", Severity = 8 }, priority: 8);
Because the lowest priority value is dequeued first, the work item with severity 1 is processed before severity 4 and 8.
Basic operations
The core operations are simple.
Enqueue
Enqueue adds an element with a priority:
queue.Enqueue("Task A", 3);
queue.Enqueue("Task B", 1);
queue.Enqueue("Task C", 2);
Peek
Peek returns the next element without removing it:
string next = queue.Peek();
Console.WriteLine(next);
If the queue is empty, Peek throws an InvalidOperationException.
When you want to avoid exceptions, use TryPeek:
if (queue.TryPeek(out string? item, out int priority))
{
Console.WriteLine($"Next item is {item} with priority {priority}");
}
Dequeue
Dequeue removes and returns the element with the lowest priority:
string item = queue.Dequeue();
If the queue is empty, Dequeue throws an InvalidOperationException.
For defensive code, prefer TryDequeue:
while (queue.TryDequeue(out string? item, out int priority))
{
Console.WriteLine($"{priority}: {item}");
}
TryDequeue is especially convenient because it gives you both the element and its priority.
A complete example
using System;
using System.Collections.Generic;
PriorityQueue<string, int> queue = new();
queue.Enqueue("Low priority background cleanup", 10);
queue.Enqueue("User-visible bug", 2);
queue.Enqueue("Production outage", 1);
queue.Enqueue("Documentation update", 8);
Console.WriteLine("Processing work items:");
while (queue.TryDequeue(out string? item, out int priority))
{
Console.WriteLine($"Priority {priority}: {item}");
}
Output:
Processing work items:
Priority 1: Production outage
Priority 2: User-visible bug
Priority 8: Documentation update
Priority 10: Low priority background cleanup
Again, the smaller number comes first.
Implementing max-priority behavior
Sometimes you want the opposite behavior: larger priority values should be returned first.
There are two common ways to do that.
The first option is to negate the priority when the priority is numeric:
PriorityQueue<string, int> queue = new();
queue.Enqueue("Normal customer", -1);
queue.Enqueue("Gold customer", -3);
queue.Enqueue("Silver customer", -2);
while (queue.TryDequeue(out string? customer, out int priority))
{
Console.WriteLine(customer);
}
Output:
Gold customer
Silver customer
Normal customer
This works, but the negative priorities can make the code less readable.
The second option is to provide a custom comparer:
using System;
using System.Collections.Generic;
IComparer<int> maxPriorityComparer = Comparer<int>.Create(
(x, y) => y.CompareTo(x));
PriorityQueue<string, int> queue = new(maxPriorityComparer);
queue.Enqueue("Normal customer", 1);
queue.Enqueue("Gold customer", 3);
queue.Enqueue("Silver customer", 2);
while (queue.TryDequeue(out string? customer, out int priority))
{
Console.WriteLine($"{priority}: {customer}");
}
Output:
3: Gold customer
2: Silver customer
1: Normal customer
This keeps the priority values natural while reversing the ordering rule.
Finding the k largest values without sorting everything
One of the most useful applications of a priority queue is finding the largest k values in a collection.
A simple solution is to sort the entire collection and take the first k elements:
var top = items
.OrderByDescending(x => x)
.Take(k)
.ToList();
That is easy to read, but it sorts the whole input. If the input contains one million values and you only need the top 10, sorting everything does unnecessary work.
A priority queue gives a better approach:
- Keep a min-priority queue with at most
kelements. - The root of the queue is the smallest value among the current top
k. - For each new value, compare it with the smallest value currently kept.
- If the new value is larger, replace the smallest kept value.
- At the end, the queue contains the top
kvalues.
The queue never grows beyond k items.
using System;
using System.Collections.Generic;
public static class TopK
{
public static IReadOnlyList<T> Largest<T>(
IEnumerable<T> source,
int k,
IComparer<T>? comparer = null)
{
if (source is null)
throw new ArgumentNullException(nameof(source));
if (k < 0)
throw new ArgumentOutOfRangeException(nameof(k));
if (k == 0)
return Array.Empty<T>();
comparer ??= Comparer<T>.Default;
PriorityQueue<T, T> queue = new(comparer);
foreach (T item in source)
{
if (queue.Count < k)
{
queue.Enqueue(item, item);
continue;
}
T smallestKept = queue.Peek();
if (comparer.Compare(item, smallestKept) > 0)
{
queue.EnqueueDequeue(item, item);
}
}
List<T> result = new(queue.Count);
while (queue.TryDequeue(out T? item, out _))
{
result.Add(item);
}
result.Reverse();
return result;
}
}
Example usage:
List<int> numbers = new() { 5, 4, 10, 7, 1, 3, 8, 1, 2, 9 };
IReadOnlyList<int> top3 = TopK.Largest(numbers, 3);
Console.WriteLine(string.Join(", ", top3));
Output:
10, 9, 8
The priority queue contains at most three elements. Every time a value smaller than the current third-largest value is found, it can be ignored.
Why this is more efficient than sorting
Sorting the full collection costs:
O(n log n)
Keeping only the top k values costs:
O(n log k)
That difference matters when k is much smaller than n.
For example, if you need the top 10 values from a collection of 1,000,000 items, the priority queue only needs to maintain a heap of 10 elements. Each useful insertion or replacement works on that small heap.
The key optimization is this line:
if (comparer.Compare(item, smallestKept) > 0)
If the new item is not better than the smallest item already in the queue, the algorithm does nothing. No insertion, no removal, no heap adjustment.
Using a priority selector
The previous example works when the element itself is also the priority, such as with numbers.
In real code, you often want to keep objects and rank them by one property.
Here is a reusable version that accepts a priority selector:
using System;
using System.Collections.Generic;
public static class TopKByPriority
{
public static IReadOnlyList<TElement> LargestBy<TElement, TPriority>(
IEnumerable<TElement> source,
int k,
Func<TElement, TPriority> prioritySelector,
IComparer<TPriority>? comparer = null)
{
if (source is null)
throw new ArgumentNullException(nameof(source));
if (prioritySelector is null)
throw new ArgumentNullException(nameof(prioritySelector));
if (k < 0)
throw new ArgumentOutOfRangeException(nameof(k));
if (k == 0)
return Array.Empty<TElement>();
comparer ??= Comparer<TPriority>.Default;
PriorityQueue<TElement, TPriority> queue = new(comparer);
foreach (TElement item in source)
{
TPriority priority = prioritySelector(item);
if (queue.Count < k)
{
queue.Enqueue(item, priority);
continue;
}
queue.TryPeek(out _, out TPriority? smallestPriority);
if (comparer.Compare(priority, smallestPriority!) > 0)
{
queue.EnqueueDequeue(item, priority);
}
}
List<TElement> result = new(queue.Count);
while (queue.TryDequeue(out TElement? item, out _))
{
result.Add(item);
}
result.Reverse();
return result;
}
}
Example:
public sealed class Product
{
public required string Name { get; init; }
public required decimal Revenue { get; init; }
}
List<Product> products = new()
{
new Product { Name = "Keyboard", Revenue = 1200m },
new Product { Name = "Mouse", Revenue = 900m },
new Product { Name = "Monitor", Revenue = 4500m },
new Product { Name = "Docking station", Revenue = 2300m },
};
IReadOnlyList<Product> topProducts = TopKByPriority.LargestBy(
products,
k: 2,
prioritySelector: product => product.Revenue);
foreach (Product product in topProducts)
{
Console.WriteLine($"{product.Name}: {product.Revenue:C}");
}
Output:
Monitor: $4,500.00
Docking station: $2,300.00
The queue stores the full Product object, but orders the heap by Revenue.
Equal priorities are not guaranteed to be FIFO
A subtle but important detail: PriorityQueue<TElement, TPriority> does not guarantee first-in, first-out behavior for elements with equal priority.
For example:
PriorityQueue<string, int> queue = new();
queue.Enqueue("First", 1);
queue.Enqueue("Second", 1);
queue.Enqueue("Third", 1);
You should not write code that depends on "First" being dequeued before "Second".
If stable ordering matters, include a sequence number in the priority:
PriorityQueue<string, (int Priority, long Sequence)> queue = new();
long sequence = 0;
queue.Enqueue("First", (1, sequence++));
queue.Enqueue("Second", (1, sequence++));
queue.Enqueue("Third", (1, sequence++));
while (queue.TryDequeue(out string? item, out _))
{
Console.WriteLine(item);
}
Output:
First
Second
Third
The priority is now a tuple. The queue first compares Priority, then compares Sequence. Since lower values come first, earlier insertions win when priorities are equal.
This is useful for schedulers, task queues, or user-facing workflows where equal-priority items should still behave predictably.
PriorityQueue is not a sorted list
A priority queue is not designed to keep all elements fully sorted.
It guarantees that the next dequeued item has the minimum priority. It does not guarantee that enumeration returns items in priority order.
This distinction matters.
If you need to repeatedly get the next best item, use PriorityQueue<TElement, TPriority>.
If you need to display all items in sorted order, use sorting:
var ordered = queue.UnorderedItems
.OrderBy(x => x.Priority)
.ToList();
The property name UnorderedItems is intentional. It lets you inspect the contents of the queue, but the enumeration order follows the internal heap layout, not a sorted order.
Useful methods beyond Enqueue and Dequeue
The basic methods are enough for many cases, but the .NET implementation includes a few useful optimizations.
EnqueueDequeue
EnqueueDequeue adds an item and then removes the minimal item as one combined heap operation.
This is useful in top-k algorithms:
queue.EnqueueDequeue(item, priority);
It is generally more efficient than calling Enqueue and then Dequeue separately.
DequeueEnqueue
DequeueEnqueue removes the minimal item and then adds a new item:
TElement removed = queue.DequeueEnqueue(newItem, newPriority);
This is useful when the queue size must remain constant and you always want to replace the current minimum.
EnqueueRange
EnqueueRange adds multiple items:
queue.EnqueueRange(new[]
{
("Task A", 3),
("Task B", 1),
("Task C", 2)
});
When building a queue from an existing collection, using the constructor or EnqueueRange can be cleaner than repeatedly calling Enqueue.
EnsureCapacity
If you already know the expected size, EnsureCapacity can reduce reallocations:
queue.EnsureCapacity(10_000);
This is useful in performance-sensitive code where the queue will grow to a known size.
TrimExcess
If a queue grew large and later became small, TrimExcess can reduce memory overhead:
queue.TrimExcess();
This is rarely needed in normal code, but it can be useful for long-lived queues.
Performance summary
For a queue with n elements:
| Operation | Typical cost | Notes |
|---|---|---|
Peek / TryPeek | O(1) | Reads the current minimum |
Enqueue | O(log n) | Inserts and restores heap order |
Dequeue / TryDequeue | O(log n) | Removes the minimum and restores heap order |
EnqueueDequeue | O(log n) | Usually better than separate enqueue and dequeue |
DequeueEnqueue | O(log n) | Usually better than separate dequeue and enqueue |
Remove | O(n) | Must scan the heap to find the element |
| Full sorting | O(n log n) | Use when you need all items ordered |
The important practical point is not just the O(log n) cost. It is that many algorithms only need a small heap.
In the top-k example, the heap size is k, not the full input size. That changes the cost from O(n log n) to O(n log k).
When to use PriorityQueue
Use PriorityQueue<TElement, TPriority> when:
- you repeatedly need the item with the smallest priority;
- new items can arrive while processing is ongoing;
- you do not need the entire collection sorted at all times;
- the best next item is more important than insertion order;
- you are implementing algorithms such as Dijkstra, A*, event simulation, or top-k selection.
Do not use it when:
- you need FIFO behavior: use
Queue<T>; - you need LIFO behavior: use
Stack<T>; - you need all items always sorted for enumeration: use
SortedSet<T>,SortedDictionary<TKey, TValue>, or sort with LINQ; - you need thread-safe producer-consumer behavior: use proper synchronization or a concurrent collection;
- you need stable ordering for equal priorities but have not included a tie-breaker.
Common pitfalls
Forgetting that lower priority comes first
This is the most common mistake.
queue.Enqueue("Very important", 100);
queue.Enqueue("Not important", 1);
In .NET, "Not important" is dequeued first because 1 is lower than 100.
Use smaller numbers for higher priority, negate numeric priorities, or provide a custom comparer.
Assuming equal priorities are stable
Equal priorities are not FIFO-guaranteed.
Add a sequence number if you need predictable ordering.
Enumerating UnorderedItems as if it were sorted
UnorderedItems does not return elements in priority order.
Use repeated Dequeue operations or explicitly sort the unordered items.
Using PriorityQueue when sorting is simpler
If you need a one-time sorted list of all elements, OrderBy is often simpler and clearer.
A priority queue becomes more interesting when you do not need all elements sorted, or when items arrive incrementally.
Conclusion
PriorityQueue<TElement, TPriority> is one of the most useful collection additions in .NET 6.
It is compact, efficient, and directly available in the base class library. Its most important behavior is that it is a min-priority queue: the element with the lowest priority value is dequeued first.
That makes it a natural fit for scheduling, graph algorithms, simulations, and top-k selection problems. It is not a sorted list, and it does not guarantee FIFO ordering for equal priorities, but when you need repeated access to the next minimum-priority element, it is exactly the right tool.
The top-k example shows why this data structure matters in practice. Instead of sorting a whole collection, you can keep only a small heap of the best candidates and reduce the cost from O(n log n) to O(n log k).
