Skip to content
Tutorials Center
My learning

Topics

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.

C#
var queue = new PriorityQueue<string, int>();
queue.Enqueue("write report", 2);
queue.Enqueue("fix outage", 1);
string next = queue.Dequeue();   // "fix outage"

Try it

C# Dequeue in priority order

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.

C# Max-heap and custom comparer

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

C#
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 with int.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. UnorderedItems lists the contents in internal heap order. To read in priority order you must dequeue.
  • Complexity: Enqueue and Dequeue are O(log n), Peek is O(1), building from a collection is O(n). EnqueueDequeue is cheaper than separate calls when you push and pop together.
  • Not thread-safe. Guard it with a lock, or use a Channel with a single consumer.
  • Availability. .NET 6 or later; it does not exist in .NET Framework.