Class PriorityNodeQueue<T>

Namespace

Stride.Core.Collections

Assembly

Stride.Core.dll

Implements a priority queue of type T.

Elements may be added to the queue in any order, but when we pull elements out of the queue, they will be returned in 'ascending' order. Adding new elements into the queue may be done at any time, so this is useful to implement a dynamically growing and shrinking queue. Both adding an element and removing the first element are log(N) operations.

The queue is implemented using a priority-heap data structure. For more details on this elegant and simple data structure see "Programming Pearls" in our library. The tree is implemented atop a list, where 2N and 2N+1 are the child nodes of node N. The tree is balanced and left-aligned so there are no 'holes' in this list.

public class PriorityNodeQueue<T>

Type Parameters

T

Type T.

Inheritance

object

PriorityNodeQueue<T>

Constructors

PriorityNodeQueue()

public PriorityNodeQueue()

PriorityNodeQueue(IComparer<T>)

public PriorityNodeQueue(IComparer<T> comparer)

Parameters

comparer IComparer<T>

Properties

Count

Returns the number of elements in the queue.

public int Count { get; }

Property Value

int

Empty

Returns true if the queue is empty.

public bool Empty { get; }

Property Value

bool

Methods

Clear()

Clear all the elements from the priority queue

public void Clear()

Dequeue()

Removes and returns the first element from the queue (least element)

public T Dequeue()

Returns

T

The first element in the queue, in ascending order.

Enqueue(PriorityQueueNode<T>)

Add an element to the priority queue - O(log(n)) time operation.

public void Enqueue(PriorityQueueNode<T> item)

Parameters

item PriorityQueueNode<T>

The item to be added to the queue

Enqueue(T)

Add an element to the priority queue - O(log(n)) time operation.

public PriorityQueueNode<T> Enqueue(T item)

Parameters

item T

The item to be added to the queue

Returns

PriorityQueueNode<T>

A node representing the item.

Peek()

Allows you to look at the first element waiting in the queue, without removing it.

public T Peek()

Returns

T

Remove(PriorityQueueNode<T>)

Removes the specified item.

public void Remove(PriorityQueueNode<T> item)

Parameters

item PriorityQueueNode<T>

The item to remove.