Loyc.Collections.MaxHeap< T, TList, TComparer > Class Template Reference

Encapsulates algorithms for a max-heap, i.e. a priority queue that always knows the largest item and can remove it in O(log Count) time, or add a new item in O(log Count) time. More...

---

Source file:

• /Core/Loyc.Collections/Heap.cs

Inheritance diagram for Loyc.Collections.MaxHeap< T, TList, TComparer >:

Remarks

Encapsulates algorithms for a max-heap, i.e. a priority queue that always knows the largest item and can remove it in O(log Count) time, or add a new item in O(log Count) time.

Template Parameters

T	Item type
TList	List type that the heap object is a wrapper for
TComparer	Type used to compare items; an instance of this type must be provided to the constructor.

Call Push(T) to add a new item, Peek() to get the largest item, and Pop() or TryPop(out bool) to remove the largest item.

Most users will want to use the derived classes MaxHeap{T} or MaxHeapInList{T} to avoid dealing with three type parameters. Ideally this type would be a struct in order to maximize performance. It is a class in order to allow derived classes including MinHeap{T}.

See also

MaxHeap{T}

Type Constraints

TList	:	IList<T>
TComparer	:	IComparer<T>

Properties
TList	List [get]
	Returns the underlying list that represents the binary heap. More...
TComparer	Comparer [get]
bool	IsEmpty [get]
int	Count [get]
Properties inherited from Loyc.Collections.IIsEmpty
bool	IsEmpty [get]
Properties inherited from Loyc.Collections.ICount
int	Count [get]
	Gets the number of items in the collection. More...

Public Member Functions
	MaxHeap (TList list, TComparer comparer, Action< T, int >?onItemMoved=null)
	Initializes the heap wrapper with the list and comparer to use. Both parameters must not be null. More...
MaxHeap< T, TList, TComparer >	Heapify ()
	Rearranges items to ensure that the underlying list has the heap property. Takes O(Count) time. More...
void	Add (T item)
	Adds an item to the heap (synonym of Push()). Complexity: O(Count). More...
void	Push (T item)
	Adds an item to the heap. Complexity: O(Count). More...
void	PriorityChanged (int index)
	Notifies the heap that the priority of the item at the specified index has changed. The item is bubbled up or down as appropriate. More...
T	PopAndPush (T item)
	Combines a pop followed by a push into one operation that is more efficient than a separate Pop nad Push(T). More...
T	TryPop (out bool isEmpty)
	Removes the largest item from the heap (or smallest item, if this is a MinHeap). More...
T	Pop ()
	Removes the largest item from the heap (or smallest item, if this is a MinHeap). More...
T	TryPeek (out bool isEmpty)
	Gets the largest item from the heap if it is not empty (or the smallest item, if this is a MinHeap). More...
T	Peek ()
	Gets the largest item from the heap (or the smallest item, if this is a MinHeap). More...

Events
Action< T, int >	OnItemMoved
	This optional callback is called whenever an item is placed into the heap, removed from the heap, or moved within the List that holds the contents of the heap. The callback is useful for certain algorithms, such as the Dijkstra algorithm, in which an object's priority may need to change while it is inside the heap. More...

Constructor & Destructor Documentation

Loyc.Collections.MaxHeap< T, TList, TComparer >.MaxHeap ( TList  list, TComparer  comparer, Action< T, int >?  onItemMoved = null  )

inline

Initializes the heap wrapper with the list and comparer to use. Both parameters must not be null.

Parameters

onItemMoved

This optional callback is called whenever an item is placed or relocated within the heap (see OnItemMoved.)

If the list is not already arranged as a max-heap, you must call Heapify() after the constructor to rearrange it into a heap.

Member Function Documentation

void Loyc.Collections.MaxHeap< T, TList, TComparer >.Add ( T  item )

inline

Adds an item to the heap (synonym of Push()). Complexity: O(Count).

MaxHeap<T, TList, TComparer> Loyc.Collections.MaxHeap< T, TList, TComparer >.Heapify ( )

inline

Rearranges items to ensure that the underlying list has the heap property. Takes O(Count) time.

Returns

this.

T Loyc.Collections.MaxHeap< T, TList, TComparer >.Peek ( )

inline

Gets the largest item from the heap (or the smallest item, if this is a MinHeap).

Exceptions

EmptySequenceException

Thrown if the List is empty.

T Loyc.Collections.MaxHeap< T, TList, TComparer >.Pop ( )

inline

Removes the largest item from the heap (or smallest item, if this is a MinHeap).

Exceptions

EmptySequenceException

Thrown if the List is empty.

T Loyc.Collections.MaxHeap< T, TList, TComparer >.PopAndPush ( T  item )

inline

Combines a pop followed by a push into one operation that is more efficient than a separate Pop nad Push(T).

void Loyc.Collections.MaxHeap< T, TList, TComparer >.PriorityChanged ( int  index )

inline

Notifies the heap that the priority of the item at the specified index has changed. The item is bubbled up or down as appropriate.

Returns

The new index of the same item.

void Loyc.Collections.MaxHeap< T, TList, TComparer >.Push ( T  item )

inline

Adds an item to the heap. Complexity: O(Count).

Implements Loyc.Collections.IPush< in T >.

T Loyc.Collections.MaxHeap< T, TList, TComparer >.TryPeek ( out bool  isEmpty )

inline

Gets the largest item from the heap if it is not empty (or the smallest item, if this is a MinHeap).

Parameters

isEmpty

Set to true if the heap is empty, false if not.

Returns

The popped value, or default(T) if the List was empty.

Implements Loyc.Collections.ITryPop< out T >.

T Loyc.Collections.MaxHeap< T, TList, TComparer >.TryPop ( out bool  isEmpty )

inline

Removes the largest item from the heap (or smallest item, if this is a MinHeap).

Parameters

isEmpty

Set to true if the heap is empty, false if not.

Returns

The popped value, or default(T) if the List was empty.

Implements Loyc.Collections.ITryPop< out T >.

Property Documentation

TList Loyc.Collections.MaxHeap< T, TList, TComparer >.List

get

Returns the underlying list that represents the binary heap.

Event Documentation

Action<T, int> Loyc.Collections.MaxHeap< T, TList, TComparer >.OnItemMoved

This optional callback is called whenever an item is placed into the heap, removed from the heap, or moved within the List that holds the contents of the heap. The callback is useful for certain algorithms, such as the Dijkstra algorithm, in which an object's priority may need to change while it is inside the heap.

In order to change an object's priority, the object must contain mutable state that represents its priority. After changing the priority, you must call PriorityChanged to inform the heap that the priority has changed. That method takes the current position of the object in the List as an argument. In order to keep track of the current position you must handle the OnItemMoved event and store the new position somewhere, such as inside the object itself.

The parameters to OnItemMoved are the object that has moved and the new index of the item within the List. If the item has been removed from the list, the index is -1.