Class PriorityQueue<TElement, TPriority>

Represents a min priority queue.

Inheritance

object

PriorityQueue<TElement, TPriority>

Namespace: GGL.Collections

Assembly: GGL.dll

Syntax

public class PriorityQueue<TElement, TPriority>

Type Parameters

Name	Description
TElement	Specifies the type of elements in the queue.
TPriority	Specifies the type of priority associated with enqueued elements.

Remarks

Implements an array-backed quaternary min-heap. Each element is enqueued with an associated priority that determines the dequeue order: elements with the lowest priority get dequeued first.

Constructors

PriorityQueue()

Initializes a new instance of the PriorityQueue<TElement, TPriority> class.

Declaration

public PriorityQueue()

PriorityQueue(IComparer<TPriority>?)

Initializes a new instance of the PriorityQueue<TElement, TPriority> class with the specified custom priority comparer.

Declaration

public PriorityQueue(IComparer<TPriority>? comparer)

Parameters

Type	Name	Description
IComparer<TPriority>	comparer	Custom comparer dictating the ordering of elements. Uses Default if the argument is null.

PriorityQueue(IEnumerable<(TElement Element, TPriority Priority)>, IComparer<TPriority>?)

Initializes a new instance of the PriorityQueue<TElement, TPriority> class that is populated with the specified elements and priorities, and with the specified custom priority comparer.

Declaration

public PriorityQueue(IEnumerable<(TElement Element, TPriority Priority)> items, IComparer<TPriority>? comparer = null)

Parameters

Type	Name	Description
IEnumerable<(TElement Element, TPriority Priority)>	items	The pairs of elements and priorities with which to populate the queue.
IComparer<TPriority>	comparer	Custom comparer dictating the ordering of elements. Uses Default if the argument is null.

Remarks

Constructs the heap using a heapify operation, which is generally faster than enqueuing individual elements sequentially.

Exceptions

Type	Condition
ArgumentNullException	The specified items argument was null.

PriorityQueue(int, IComparer<TPriority>?)

Initializes a new instance of the PriorityQueue<TElement, TPriority> class with the specified initial capacity and custom priority comparer.

Declaration

public PriorityQueue(int initialCapacity, IComparer<TPriority>? comparer = null)

Parameters

Type	Name	Description
int	initialCapacity	Initial capacity to allocate in the underlying heap array.
IComparer<TPriority>	comparer	Custom comparer dictating the ordering of elements. Uses Default if the argument is null.

Exceptions

Type	Condition
ArgumentOutOfRangeException	The specified initialCapacity was negative.

Properties

Comparer

Gets the priority comparer used by the PriorityQueue<TElement, TPriority>.

Declaration

public IComparer<TPriority> Comparer { get; }

Property Value

Type	Description
IComparer<TPriority>	Represents a min priority queue.

Count

Gets the number of elements contained in the PriorityQueue<TElement, TPriority>.

Declaration

public int Count { get; }

Property Value

Type	Description
int	Represents a min priority queue.

UnorderedItems

Gets a collection that enumerates the elements of the queue in an unordered manner.

Declaration

public PriorityQueue<TElement, TPriority>.UnorderedItemsCollection UnorderedItems { get; }

Property Value

Type	Description
PriorityQueue<TElement, TPriority>.UnorderedItemsCollection	Represents a min priority queue.

Remarks

The enumeration does not order items by priority, since that would require N * log(N) time and N space. Items are instead enumerated following the internal array heap layout.

Methods

Clear()

Removes all items from the PriorityQueue<TElement, TPriority>.

Declaration

public void Clear()

Dequeue()

Removes and returns the minimal element from the PriorityQueue<TElement, TPriority>.

Declaration

public TElement Dequeue()

Returns

Type	Description
TElement	The minimal element of the PriorityQueue<TElement, TPriority>.

Exceptions

Type	Condition
InvalidOperationException	The queue is empty.

DequeueEnqueue(TElement, TPriority)

Removes the minimal element and then immediately adds the specified element with associated priority to the PriorityQueue<TElement, TPriority>,

Declaration

public TElement DequeueEnqueue(TElement element, TPriority priority)

Parameters

Type	Name	Description
TElement	element	The element to add to the PriorityQueue<TElement, TPriority>.
TPriority	priority	The priority with which to associate the new element.

Returns

Type	Description
TElement	The minimal element removed before performing the enqueue operation.

Remarks

Implements an extract-then-insert heap operation that is generally more efficient than sequencing Dequeue and Enqueue operations: in the worst case scenario only one shift-down operation is required.

Exceptions

Type	Condition
InvalidOperationException	The queue is empty.

Enqueue(TElement, TPriority)

Adds the specified element with associated priority to the PriorityQueue<TElement, TPriority>.

Declaration

public void Enqueue(TElement element, TPriority priority)

Parameters

Type	Name	Description
TElement	element	The element to add to the PriorityQueue<TElement, TPriority>.
TPriority	priority	The priority with which to associate the new element.

EnqueueDequeue(TElement, TPriority)

Adds the specified element with associated priority to the PriorityQueue<TElement, TPriority>, and immediately removes the minimal element, returning the result.

Declaration

public TElement EnqueueDequeue(TElement element, TPriority priority)

Parameters

Type	Name	Description
TElement	element	The element to add to the PriorityQueue<TElement, TPriority>.
TPriority	priority	The priority with which to associate the new element.

Returns

Type	Description
TElement	The minimal element removed after the enqueue operation.

Remarks

Implements an insert-then-extract heap operation that is generally more efficient than sequencing Enqueue and Dequeue operations: in the worst case scenario only one shift-down operation is required.

EnqueueRange(IEnumerable<(TElement Element, TPriority Priority)>)

Enqueues a sequence of element/priority pairs to the PriorityQueue<TElement, TPriority>.

Declaration

public void EnqueueRange(IEnumerable<(TElement Element, TPriority Priority)> items)

Parameters

Type	Name	Description
IEnumerable<(TElement Element, TPriority Priority)>	items	The pairs of elements and priorities to add to the queue.

Exceptions

Type	Condition
ArgumentNullException	The specified items argument was null.

EnqueueRange(IEnumerable<TElement>, TPriority)

Enqueues a sequence of elements pairs to the PriorityQueue<TElement, TPriority>, all associated with the specified priority.

Declaration

public void EnqueueRange(IEnumerable<TElement> elements, TPriority priority)

Parameters

Type	Name	Description
IEnumerable<TElement>	elements	The elements to add to the queue.
TPriority	priority	The priority to associate with the new elements.

Exceptions

Type	Condition
ArgumentNullException	The specified elements argument was null.

EnsureCapacity(int)

Ensures that the PriorityQueue<TElement, TPriority> can hold up to capacity items without further expansion of its backing storage.

Declaration

public int EnsureCapacity(int capacity)

Parameters

Type	Name	Description
int	capacity	The minimum capacity to be used.

Returns

Type	Description
int	The current capacity of the PriorityQueue<TElement, TPriority>.

Exceptions

Type	Condition
ArgumentOutOfRangeException	The specified capacity is negative.

Peek()

Returns the minimal element from the PriorityQueue<TElement, TPriority> without removing it.

Declaration

public TElement Peek()

Returns

Type	Description
TElement	The minimal element of the PriorityQueue<TElement, TPriority>.

Exceptions

Type	Condition
InvalidOperationException	The PriorityQueue<TElement, TPriority> is empty.

TrimExcess()

Sets the capacity to the actual number of items in the PriorityQueue<TElement, TPriority>, if that is less than 90 percent of current capacity.

Declaration

public void TrimExcess()

Remarks

This method can be used to minimize a collection's memory overhead if no new elements will be added to the collection.

TryDequeue(out TElement, out TPriority)

Removes the minimal element from the PriorityQueue<TElement, TPriority>, and copies it to the element parameter, and its associated priority to the priority parameter.

Declaration

public bool TryDequeue(out TElement element, out TPriority priority)

Parameters

Type	Name	Description
TElement	element	The removed element.
TPriority	priority	The priority associated with the removed element.

Returns

Type	Description
bool	true if the element is successfully removed; false if the PriorityQueue<TElement, TPriority> is empty.

TryPeek(out TElement, out TPriority)

Returns a value that indicates whether there is a minimal element in the PriorityQueue<TElement, TPriority>, and if one is present, copies it to the element parameter, and its associated priority to the priority parameter. The element is not removed from the PriorityQueue<TElement, TPriority>.

Declaration

public bool TryPeek(out TElement element, out TPriority priority)

Parameters

Type	Name	Description
TElement	element	The minimal element in the queue.
TPriority	priority	The priority associated with the minimal element.

Returns

Type	Description
bool	true if there is a minimal element; false if the PriorityQueue<TElement, TPriority> is empty.