Class FibonacciHeap<T, TKey>
Fibonacci Heap realization. Uses generic type T for data storage and TKey as a key type.
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: Mars.Common.Collections
Assembly: Mars.Common.dll
Syntax
public class FibonacciHeap<T, TKey>
where TKey : IComparable<TKey>
Type Parameters
Name | Description |
---|---|
T | Type of the stored objects. |
TKey | Type of the object key. Should implement IComparable. |
Constructors
| Improve this Doc View SourceFibonacciHeap(TKey)
Initializes the new instance of the Heap.
Declaration
public FibonacciHeap(TKey minKeyValue)
Parameters
Type | Name | Description |
---|---|---|
TKey | minKeyValue | Minimum value of the key - to be used for comparing. |
Properties
| Improve this Doc View SourceCount
Gets the actual amount elements in this this heap.
Access in O(1).
Declaration
public int Count { get; }
Property Value
Type | Description |
---|---|
System.Int32 | Returns the current amount of elements in the heap. |
Methods
| Improve this Doc View SourceClear()
Removes all the elements from the heap.
Declaration
public void Clear()
DecreaseKey(FibonacciHeapNode<T, TKey>, TKey)
Decreases the key of a node. O(1) amortized.
Declaration
public void DecreaseKey(FibonacciHeapNode<T, TKey> x, TKey k)
Parameters
Type | Name | Description |
---|---|---|
FibonacciHeapNode<T, TKey> | x | |
TKey | k |
Delete(FibonacciHeapNode<T, TKey>)
Deletes a node from the heap. O(log n)
Declaration
public void Delete(FibonacciHeapNode<T, TKey> x)
Parameters
Type | Name | Description |
---|---|---|
FibonacciHeapNode<T, TKey> | x |
Insert(FibonacciHeapNode<T, TKey>)
Inserts a new node with its key. O(1)
Declaration
public void Insert(FibonacciHeapNode<T, TKey> node)
Parameters
Type | Name | Description |
---|---|---|
FibonacciHeapNode<T, TKey> | node |
IsEmpty()
Identifies whatever heap is empty.
Declaration
public bool IsEmpty()
Returns
Type | Description |
---|---|
System.Boolean | true if heap is empty - contains no elements. |
Min()
Gets the smallest node of this min-fibonacci heap
Access is O(1)
Declaration
public FibonacciHeapNode<T, TKey> Min()
Returns
Type | Description |
---|---|
FibonacciHeapNode<T, TKey> | Returns the smallest node of the heap or null if the heap is empty. O(1) |
RemoveMin()
Removes the smallest node of the heap and selects the next one as smallest node.
Access in O(log n) amortized
Declaration
public FibonacciHeapNode<T, TKey> RemoveMin()
Returns
Type | Description |
---|---|
FibonacciHeapNode<T, TKey> | Returns the removed nodes which was the smallest in the heap. |
Union(FibonacciHeap<T, TKey>, FibonacciHeap<T, TKey>)
Joins two heaps. O(1)
Declaration
public static FibonacciHeap<T, TKey> Union(FibonacciHeap<T, TKey> h1, FibonacciHeap<T, TKey> h2)
Parameters
Type | Name | Description |
---|---|---|
FibonacciHeap<T, TKey> | h1 | |
FibonacciHeap<T, TKey> | h2 |
Returns
Type | Description |
---|---|
FibonacciHeap<T, TKey> |