Britbot.PriorityQueue.HeapPriorityQueue< T > Class Template Reference

An implementation of a min-Priority Queue using a heap. Has O(1) .Contains()! See https://bitbucket.org/BlueRaja/high-speed-priority-queue-for-c/wiki/Getting%20Started for more information. More...

Inheritance diagram for Britbot.PriorityQueue.HeapPriorityQueue< T >:

Collaboration diagram for Britbot.PriorityQueue.HeapPriorityQueue< T >:

List of all members.

Public Member Functions
	HeapPriorityQueue (int maxNodes)
	Instantiate a new Priority Queue.
void	Set (HeapPriorityQueue< T > queue)
	Copy c'tor.
void	Clear ()
	Removes every node from the queue. O(n) (So, don't do this often!)
bool	Contains (T node)
	Returns (in O(1)!) whether the given node is in the queue. O(1)
void	Enqueue (T node, double priority)
	Enqueue a node - .Priority must be set beforehand! O(log n)
T	Dequeue ()
	Removes the head of the queue (node with highest priority; ties are broken by order of insertion), and returns it. O(log n)
void	UpdatePriority (T node, double priority)
	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! O(log n)
void	Remove (T node)
	Removes a node from the queue. Note that the node does not need to be the head of the queue. O(log n)
IEnumerator< T >	GetEnumerator ()
bool	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.
Properties
int	Count [get, set]
	Returns the number of nodes in the queue. O(1)
int	MaxSize [get]
	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 throw an exception. O(1)
T	First [get]
	Returns the head of the queue, without removing it (use Dequeue() for that). O(1)
Private Member Functions
void	Swap (T node1, T node2)
void	CascadeUp (T node)
void	CascadeDown (T node)
bool	HasHigherPriority (T higher, T lower)
	Returns true if 'higher' has higher priority than 'lower', false otherwise. Note that calling HasHigherPriority(node, node) (ie. both arguments the same node) will return false.
void	OnNodeUpdated (T node)
IEnumerator IEnumerable.	GetEnumerator ()
Private Attributes
T[]	_nodes
long	_numNodesEverEnqueued

---

Detailed Description

template<T>
class Britbot::PriorityQueue::HeapPriorityQueue< T >

An implementation of a min-Priority Queue using a heap. Has O(1) .Contains()! See https://bitbucket.org/BlueRaja/high-speed-priority-queue-for-c/wiki/Getting%20Started for more information.

Template Parameters:

T	The values in the queue. Must implement the PriorityQueueNode interface

Type Constraints

T

:

PriorityQueueNode

Definition at line 16 of file HeapPriorityQueue.cs.

---

The documentation for this class was generated from the following file:

• PriorityQueue/HeapPriorityQueue.cs