Class FastPriorityQueue<T>

An implementation of a min-Priority Queue using a heap. Has O(1) .Contains()! See https://github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp/wiki/Getting-Started for more information

Inheritance
System.Object
FastPriorityQueue<T>
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 sealed class FastPriorityQueue<T> : IPriorityQueue<T, float> where T : FastPriorityQueueNode
Type Parameters
T

The values in the queue. Must extend the FastPriorityQueueNode class

Constructors

FastPriorityQueue(Int32)

Instantiate a new Priority Queue

Declaration
public FastPriorityQueue(int maxNodes)
Parameters
System.Int32 maxNodes

The max nodes ever allowed to be enqueued (going over this will cause undefined behavior)

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). If the queue is empty, behavior is undefined. O(1)

Declaration
public T First { get; }
Property Value
T

Implements

MaxSize

Returns the maximum number of items that can be enqueued at once in this queue. Once you hit this number (ie. once Count == MaxSize), attempting to enqueue another item will cause undefined behavior. O(1)

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

Methods

Clear()

Removes every node from the queue. O(n) (So, don't do this often!)

Declaration
public void Clear()
Implements

Contains(T)

Returns (in O(1)!) whether the given node is in the queue. O(1)

Declaration
public bool Contains(T node)
Parameters
T node

Returns
System.Boolean

Implements

Dequeue()

Removes the head of the queue and returns it. If queue is empty, result is undefined O(log n)

Declaration
public T Dequeue()
Returns
T

Implements

Enqueue(T, Single)

Enqueue a node to the priority queue. Lower values are placed in front. Ties are broken by first-in-first-out. If the queue is full, the result is undefined. If the node is already enqueued, the result is undefined. O(log n)

Declaration
public void Enqueue(T node, float priority)
Parameters
T node

System.Single priority

Implements

GetEnumerator()

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

IsValidQueue()

Should not be called in production code. Checks to make sure the queue is still in a valid state. Used for testing/debugging the queue.

Declaration
public bool IsValidQueue()
Returns
System.Boolean

Remove(T)

Removes a node from the queue. The node does not need to be the head of the queue.
If the node is not in the queue, the result is undefined. If unsure, check Contains() first O(log n)

Declaration
public void Remove(T node)
Parameters
T node

Implements

Resize(Int32)

Resize the queue so it can accept more nodes. All currently enqueued nodes are remain. Attempting to decrease the queue size to a size too small to hold the existing nodes results in undefined behavior O(n)

Declaration
public void Resize(int maxNodes)
Parameters
System.Int32 maxNodes

UpdatePriority(T, Single)

This method must be called on a node every time its priority changes while it is in the queue.
Forgetting to call this method will result in a corrupted queue! Calling this method on a node not in the queue results in undefined behavior O(log n)

Declaration
public void UpdatePriority(T node, float priority)
Parameters
T node

System.Single priority

Implements