Class SimplePriorityQueue<TItem, TPriority>

A simplified priority queue implementation. Is stable, auto-resizes, and thread-safe, at the cost of being slightly slower than FastPriorityQueue

Inheritance
System.Object
SimplePriorityQueue<TItem, TPriority>
SimplePriorityQueue<TItem>
Inherited Members
System.Object.ToString()
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
Namespace: System.Dynamic.ExpandoObject
Syntax
public class SimplePriorityQueue<TItem, TPriority> : IPriorityQueue<TItem, TPriority> where TPriority : IComparable<TPriority>
Type Parameters
TItem

The type to enqueue
TPriority

The priority-type to use for nodes. Must extend IComparable<TPriority>

Constructors

SimplePriorityQueue()

Declaration
public SimplePriorityQueue()

Properties

Count

Returns the number of nodes in the queue. O(1)

Declaration
public int Count { get; }
Property Value
System.Int32

Implements

First

Returns the head of the queue, without removing it (use Dequeue() for that). Throws an exception when the queue is empty. O(1)

Declaration
public TItem First { get; }
Property Value
TItem

Implements

Methods

Clear()

Removes every node from the queue. O(n)

Declaration
public void Clear()
Implements

Contains(TItem)

Returns whether the given item is in the queue. O(n)

Declaration
public bool Contains(TItem item)
Parameters
TItem item

Returns
System.Boolean

Implements

Dequeue()

Removes the head of the queue (node with minimum priority; ties are broken by order of insertion), and returns it. If queue is empty, throws an exception O(log n)

Declaration
public TItem Dequeue()
Returns
TItem

Implements

Enqueue(TItem, TPriority)

Enqueue a node to the priority queue. Lower values are placed in front. Ties are broken by first-in-first-out. This queue automatically resizes itself, so there's no concern of the queue becoming 'full'. Duplicates are allowed. O(log n)

Declaration
public void Enqueue(TItem item, TPriority priority)
Parameters
TItem item

TPriority priority

Implements

GetEnumerator()

Declaration
public IEnumerator<TItem> GetEnumerator()
Returns
IEnumerator<TItem>

IsValidQueue()

Declaration
public bool IsValidQueue()
Returns
System.Boolean

Remove(TItem)

Removes an item from the queue. The item does not need to be the head of the queue.
If the item is not in the queue, an exception is thrown. If unsure, check Contains() first. If multiple copies of the item are enqueued, only the first one is removed. O(n)

Declaration
public void Remove(TItem item)
Parameters
TItem item

Implements

UpdatePriority(TItem, TPriority)

Call this method to change the priority of an item. Calling this method on a item not in the queue will throw an exception. If the item is enqueued multiple times, only the first one will be updated. (If your requirements are complex enough that you need to enqueue the same item multiple times and be able to update all of them, please wrap your items in a wrapper class so they can be distinguished). O(n)

Declaration
public void UpdatePriority(TItem item, TPriority priority)
Parameters
TItem item

TPriority priority

Implements