Loyc.Collections.MinHeap< T > Class Template Reference

This is 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. The ToMinHeap extension method returns this type. More...

---

Source file:

• /Core/Loyc.Collections/Heap.cs

Inheritance diagram for Loyc.Collections.MinHeap< T >:

Remarks

This is 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. The ToMinHeap extension method returns this type.

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.

Public Member Functions
	MinHeap (IComparer< T >?comparer=null, Action< T, int >?onItemMoved=null)
	MinHeap (IEnumerable< T > items, IComparer< T >?comparer=null, bool heapify=true)
	MinHeap (InternalList< T > list, IComparer< T >?comparer=null, bool heapify=true)
Public Member Functions inherited from Loyc.Collections.MinHeap< T, TList, TComparer >
	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...