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

Encapsulates algorithms for a min-heap, i.e. a priority queue that always knows the smallest 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.MinHeap< T, TList, TComparer >:

Remarks

Encapsulates algorithms for a min-heap, i.e. a priority queue that always knows the smallest 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 smallest item, and Pop() or TryPop(out bool) to remove the smallest item.

Most users will want to use the derived classes MinHeap{T} or MinHeapInList{T} to avoid dealing with three type parameters. Ideally this type would be a struct in order to maximize performance. It is a class so that it can re-use the code in MaxHeap{T, TList, TComparer}.

See also

MinHeap{T}

Type Constraints

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

Public Member Functions
	MinHeap (TList list, TComparer comparer, Action< T, int >?onItemMoved=null)
Public Member Functions inherited from Loyc.Collections.MaxHeap< T, TList, TComparer >
	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...

Additional Inherited Members
Properties inherited from Loyc.Collections.MaxHeap< T, TList, TComparer >
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...
Events inherited from Loyc.Collections.MaxHeap< T, TList, TComparer >
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...