IndexedPriorityQueue<TElement, TPriority> Class

Definition

Namespace

Bodu.Collections.Generic

Assembly

Bodu.Collections.dll

Package

Bodu.Collections 1.0.0

Source

IndexedPriorityQueue{T,T}.Enumerator.cs

Represents a binary min-heap priority queue keyed by element identity, supporting O(log n) re-prioritization (decrease- or increase-key) and removal of any element by value.

public sealed class IndexedPriorityQueue<TElement, TPriority> : IReadOnlyCollection<KeyValuePair<TElement, TPriority>>, IEnumerable<KeyValuePair<TElement, TPriority>>, ICollection, IEnumerable where TElement : notnull

Type Parameters

TElement

Specifies the non-null element type used as the queue's identity.

TPriority

Specifies the priority type used for ordering.

Inheritance

object

IndexedPriorityQueue<TElement, TPriority>

Implements

IReadOnlyCollection<KeyValuePair<TElement, TPriority>>

IEnumerable<KeyValuePair<TElement, TPriority>>

ICollection

IEnumerable

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

ComparableExtensions.AtLeast<T>(T, T, IComparer<T>)

ComparableExtensions.AtMost<T>(T, T, IComparer<T>)

ComparableExtensions.IsEqualTo<T>(T, T, IComparer<T>)

ComparableExtensions.Max<T>(T, T, IComparer<T>)

ComparableExtensions.Min<T>(T, T, IComparer<T>)

Examples

// Dijkstra-style relaxation: the tentative cost of each node is its priority, and an improved
// path arrives as a re-prioritization rather than a duplicate enqueue.
var queue = new IndexedPriorityQueue<string, int>();

queue.Enqueue("A", 5);
queue.Enqueue("B", 9);
queue.Enqueue("C", 2);

queue.Update("B", 3);                  // B's tentative cost improved
queue.EnqueueOrUpdate("D", 7);         // adds D if absent, updates otherwise

string next = queue.Dequeue();         // "C" - smallest priority
bool hasD   = queue.TryGetPriority("D", out int priority); // true, priority == 7

Remarks

IndexedPriorityQueue<TElement, TPriority> complements PriorityQueue<TElement, TPriority> by maintaining an auxiliary element-to-index map alongside the heap. This map turns Contains(TElement), TryGetPriority(TElement, out TPriority), and the slot lookup used by Update(TElement, TPriority), Remove(TElement), and EnqueueOrUpdate(TElement, TPriority) into O(1) operations and the subsequent heap repair into O(log n) - the operations Dijkstra's algorithm, Prim's algorithm, and A* require.

Elements must be non-null and unique within the queue. Enqueue(TElement, TPriority) throws ArgumentNullException if the element is null or ArgumentException if the element is already present; use EnqueueOrUpdate(TElement, TPriority) for set semantics.

Ordering is determined by an IComparer<T>; smaller priorities are dequeued first (min-heap). To obtain max-heap behavior, supply a reversed comparer. Element identity uses an IEqualityComparer<T>; both default to the framework default comparer when not specified.

Enumeration walks the underlying heap array in storage order, not priority order. Dequeue items in turn to obtain priority-ordered output.

IndexedPriorityQueue<TElement, TPriority> is not thread-safe. Concurrent reads and writes require external synchronization.

Constructors

IndexedPriorityQueue()

Initializes a new instance of the IndexedPriorityQueue<TElement, TPriority> class with zero initial capacity, the default priority comparer, and the default element comparer.

public IndexedPriorityQueue()

IndexedPriorityQueue(IComparer<TPriority>?)

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

public IndexedPriorityQueue(IComparer<TPriority>? priorityComparer)

Parameters

priorityComparer IComparer<TPriority>

The comparer used to order priorities, or null to use Default.

IndexedPriorityQueue(IEnumerable<KeyValuePair<TElement, TPriority>>)

Initializes a new instance of the IndexedPriorityQueue<TElement, TPriority> class containing the supplied element-priority pairs, heapified in O(n).

public IndexedPriorityQueue(IEnumerable<KeyValuePair<TElement, TPriority>> items)

Parameters

items IEnumerable<KeyValuePair<TElement, TPriority>>

The element-priority pairs used to populate the queue. Element keys must be unique. Must not be null.

Exceptions

ArgumentNullException

items is null.

ArgumentException

items contains a duplicate element key.

IndexedPriorityQueue(IEnumerable<KeyValuePair<TElement, TPriority>>, IComparer<TPriority>?, IEqualityComparer<TElement>?)

Initializes a new instance of the IndexedPriorityQueue<TElement, TPriority> class containing the supplied element-priority pairs, with the specified priority and element comparers.

public IndexedPriorityQueue(IEnumerable<KeyValuePair<TElement, TPriority>> items, IComparer<TPriority>? priorityComparer, IEqualityComparer<TElement>? elementComparer)

Parameters

items IEnumerable<KeyValuePair<TElement, TPriority>>

The element-priority pairs used to populate the queue. Element keys must be unique. Must not be null.

priorityComparer IComparer<TPriority>

The comparer used to order priorities, or null to use Default.

elementComparer IEqualityComparer<TElement>

The comparer used to test element equality, or null to use Default.

Remarks

When items implements ICollection<T> the backing array is allocated up-front to its Count and the heap is built bottom-up in O(n); otherwise the array grows on demand as items are appended.

Exceptions

ArgumentNullException

items is null.

ArgumentException

items contains a duplicate element key.

IndexedPriorityQueue(int)

Initializes a new instance of the IndexedPriorityQueue<TElement, TPriority> class with the specified initial capacity, using the default priority comparer and element comparer.

public IndexedPriorityQueue(int capacity)

Parameters

capacity int

The initial capacity of the heap. Must be non-negative.

Exceptions

ArgumentOutOfRangeException

capacity is negative.

IndexedPriorityQueue(int, IComparer<TPriority>?)

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

public IndexedPriorityQueue(int capacity, IComparer<TPriority>? priorityComparer)

Parameters

capacity int

The initial capacity of the heap. Must be non-negative.

priorityComparer IComparer<TPriority>

The comparer used to order priorities, or null to use Default.

Exceptions

ArgumentOutOfRangeException

capacity is negative.

IndexedPriorityQueue(int, IComparer<TPriority>?, IEqualityComparer<TElement>?)

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

public IndexedPriorityQueue(int capacity, IComparer<TPriority>? priorityComparer, IEqualityComparer<TElement>? elementComparer)

Parameters

capacity int

The initial capacity of the heap. Must be non-negative.

priorityComparer IComparer<TPriority>

The comparer used to order priorities, or null to use Default.

elementComparer IEqualityComparer<TElement>

The comparer used to test element equality, or null to use Default.

Exceptions

ArgumentOutOfRangeException

capacity is negative.

Properties

Capacity

Gets the total number of elements the internal data structure can hold without resizing.

public int Capacity { get; }

Property Value

int

The length of the internal heap array.

Comparer

Gets the priority comparer used by the queue to order elements.

public IComparer<TPriority> Comparer { get; }

Property Value

IComparer<TPriority>

The configured IComparer<T>.

Count

Gets the number of elements contained in the queue.

public int Count { get; }

Property Value

int

The current element count.

ElementComparer

Gets the element equality comparer used by the queue to identify elements.

public IEqualityComparer<TElement> ElementComparer { get; }

Property Value

IEqualityComparer<TElement>

The configured IEqualityComparer<T>.

Methods

Clear()

Removes all elements from the queue.

public void Clear()

Remarks

The backing capacity is preserved; call TrimExcess() to release the unused storage.

Contains(TElement)

Determines whether the queue contains the specified element.

public bool Contains(TElement element)

Parameters

element TElement

The element to locate. Must not be null.

Returns

bool

true if the element is present; otherwise, false.

Exceptions

ArgumentNullException

element is null.

Dequeue()

Removes and returns the element-priority pair at the head of the queue.

public KeyValuePair<TElement, TPriority> Dequeue()

Returns

KeyValuePair<TElement, TPriority>

The dequeued element-priority pair.

Exceptions

InvalidOperationException

The queue is empty.

Enqueue(TElement, TPriority)

Adds the specified element with the specified priority. The element must not already be present.

public void Enqueue(TElement element, TPriority priority)

Parameters

element TElement

The element to add. Must not be null.

priority TPriority

The priority associated with the element.

Exceptions

ArgumentNullException

element is null.

ArgumentException

element is already present in the queue.

EnqueueOrUpdate(TElement, TPriority)

Adds the specified element with the specified priority, or re-prioritizes it if already present.

public bool EnqueueOrUpdate(TElement element, TPriority priority)

Parameters

element TElement

The element to add or update. Must not be null.

priority TPriority

The priority to assign.

Returns

bool

true if the element was added; false if an existing entry was updated.

Remarks

This is the canonical primitive for Dijkstra-style relaxation steps.

Exceptions

ArgumentNullException

element is null.

EnsureCapacity(int)

Ensures that the internal storage can hold at least capacity elements without reallocating.

public int EnsureCapacity(int capacity)

Parameters

capacity int

The minimum capacity to ensure. Must be non-negative.

Returns

int

The new capacity of the internal storage.

Exceptions

ArgumentOutOfRangeException

capacity is negative.

GetEnumerator()

Returns a struct enumerator that walks the heap storage in array order.

public IndexedPriorityQueue<TElement, TPriority>.Enumerator GetEnumerator()

Returns

IndexedPriorityQueue<TElement, TPriority>.Enumerator

A new IndexedPriorityQueue<TElement, TPriority>.Enumerator bound to this queue.

Remarks

Enumeration is in heap-storage order, not priority order. To enumerate in priority order, drain the queue with successive Dequeue() calls.

GetPriority(TElement)

Retrieves the priority associated with the specified element.

public TPriority GetPriority(TElement element)

Parameters

element TElement

The element whose priority is to be retrieved. Must not be null.

Returns

TPriority

The priority currently associated with element.

Exceptions

ArgumentNullException

element is null.

KeyNotFoundException

element is not present in the queue.

Peek()

Returns the element-priority pair at the head of the queue without removing it.

public KeyValuePair<TElement, TPriority> Peek()

Returns

KeyValuePair<TElement, TPriority>

The element-priority pair with the smallest priority per the configured comparer.

Exceptions

InvalidOperationException

The queue is empty.

Remove(TElement)

Removes the specified element from the queue if present.

public bool Remove(TElement element)

Parameters

element TElement

The element to remove. Must not be null.

Returns

bool

true if the element was found and removed; otherwise, false.

Exceptions

ArgumentNullException

element is null.

TrimExcess()

Reduces the internal storage to match the current element count.

public void TrimExcess()

Remarks

This method does not bump the modification version: enumerators remain valid.

TryDequeue(out TElement, out TPriority)

Attempts to remove and return the element-priority pair at the head of the queue.

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

Parameters

element TElement

When this method returns, contains the dequeued element if successful; otherwise, the default value of TElement.

priority TPriority

When this method returns, contains the dequeued priority if successful; otherwise, the default value of TPriority.

Returns

bool

true if an element was dequeued; otherwise, false.

TryEnqueue(TElement, TPriority)

Attempts to add the specified element with the specified priority.

public bool TryEnqueue(TElement element, TPriority priority)

Parameters

element TElement

The element to add. Must not be null.

priority TPriority

The priority associated with the element.

Returns

bool

true if the element was added; false if it was already present.

Exceptions

ArgumentNullException

element is null.

TryGetPriority(TElement, out TPriority)

Attempts to retrieve the priority associated with the specified element.

public bool TryGetPriority(TElement element, out TPriority priority)

Parameters

element TElement

The element whose priority is to be retrieved. Must not be null.

priority TPriority

When this method returns, contains the priority associated with element if found; otherwise, the default value of TPriority.

Returns

bool

true if the element was found; otherwise, false.

Exceptions

ArgumentNullException

element is null.

TryPeek(out TElement, out TPriority)

Attempts to retrieve the element-priority pair at the head of the queue without removing it.

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

Parameters

element TElement

When this method returns, contains the head element if the queue is non-empty; otherwise, the default value of TElement.

priority TPriority

When this method returns, contains the head priority if the queue is non-empty; otherwise, the default value of TPriority.

Returns

bool

true if a head element was retrieved; otherwise, false.

TryUpdate(TElement, TPriority)

Attempts to re-prioritize the specified element.

public bool TryUpdate(TElement element, TPriority priority)

Parameters

element TElement

The element to re-prioritize. Must not be null.

priority TPriority

The new priority to assign.

Returns

bool

true if the element was found and updated; otherwise, false.

Exceptions

ArgumentNullException

element is null.

Update(TElement, TPriority)

Re-prioritizes the specified element. The element must already be present.

public void Update(TElement element, TPriority priority)

Parameters

element TElement

The element to re-prioritize. Must not be null.

priority TPriority

The new priority to assign.

Remarks

Works for both decrease-key and increase-key. Cost is O(log n) and includes a single sift-up or sift-down of the moved node; if the priority is unchanged the operation is a no-op.

Exceptions

ArgumentNullException

element is null.

KeyNotFoundException

element is not present in the queue.

Explicit Interface Implementations

IEnumerable<KeyValuePair<TElement, TPriority>>.GetEnumerator()

Returns an enumerator that iterates through the collection.

IEnumerator<KeyValuePair<TElement, TPriority>> IEnumerable<KeyValuePair<TElement, TPriority>>.GetEnumerator()

Returns

IEnumerator<KeyValuePair<TElement, TPriority>>

An enumerator that can be used to iterate through the collection.

ICollection.CopyTo(Array, int)

Copies the queue's element-priority pairs to the specified array, starting at the specified index, in heap-storage order.

void ICollection.CopyTo(Array array, int index)

Parameters

array Array

The destination array. Must be single-dimensional, zero-based, and have an element type compatible with KeyValuePair<TKey, TValue>.

index int

The zero-based starting index in array.

Exceptions

ArgumentNullException

array is null.

ArgumentOutOfRangeException

index is negative.

ArgumentException

array is multidimensional, not zero-based, has an incompatible element type, or has insufficient room from index onward. When thrown for an incompatible element type, array is left unmodified (no elements are written).

ICollection.IsSynchronized

Gets a value indicating whether access to the queue is synchronized (thread-safe). Always returns false; IndexedPriorityQueue<TElement, TPriority> is not thread-safe.

bool ICollection.IsSynchronized { get; }

Returns

bool

Always false.

ICollection.SyncRoot

Gets a lazily-initialized object that can be used to synchronize access to the queue.

object ICollection.SyncRoot { get; }

Returns

object

A non-null object suitable as a Monitor target.

IEnumerable.GetEnumerator()

Returns an enumerator that iterates through a collection.

IEnumerator IEnumerable.GetEnumerator()

Returns

IEnumerator

An IEnumerator object that can be used to iterate through the collection.

Applies to

Product	Versions
.NET	8, 10