Skip to content

Commit 5db2d40

Browse files
justcoding121justcoding121
committed
fix Fibonacci spelling
1 parent b466c70 commit 5db2d40

File tree

9 files changed

+43
-43
lines changed

9 files changed

+43
-43
lines changed

‎README.md

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -74,7 +74,7 @@ Supports
7474
- [X] Binary heap ([implementation](https://github.com/justcoding121/Advanced-Algorithms/blob/master/src/Advanced.Algorithms/DataStructures/Heap/BHeap.cs) | [tests](https://github.com/justcoding121/Advanced-Algorithms/blob/master/tests/Advanced.Algorithms.Tests/DataStructures/Heap/BHeap_Tests.cs))
7575
- [X] d-ary heap ([implementation](https://github.com/justcoding121/Advanced-Algorithms/blob/master/src/Advanced.Algorithms/DataStructures/Heap/d-aryHeap.cs) | [tests](https://github.com/justcoding121/Advanced-Algorithms/blob/master/tests/Advanced.Algorithms.Tests/DataStructures/Heap/D-aryHeap_Tests.cs))
7676
- [X] Binomial heap ([implementation](https://github.com/justcoding121/Advanced-Algorithms/blob/master/src/Advanced.Algorithms/DataStructures/Heap/BinomialHeap.cs) | [tests](https://github.com/justcoding121/Advanced-Algorithms/blob/master/tests/Advanced.Algorithms.Tests/DataStructures/Heap/BinomialHeap_Tests.cs))
77-
- [X] Fibornacci heap ([implementation](https://github.com/justcoding121/Advanced-Algorithms/blob/master/src/Advanced.Algorithms/DataStructures/Heap/FibornacciHeap.cs) | [tests](https://github.com/justcoding121/Advanced-Algorithms/blob/master/tests/Advanced.Algorithms.Tests/DataStructures/Heap/FibornacciHeap_Tests.cs))
77+
- [X] Fibonacci heap ([implementation](https://github.com/justcoding121/Advanced-Algorithms/blob/master/src/Advanced.Algorithms/DataStructures/Heap/FibonacciHeap.cs) | [tests](https://github.com/justcoding121/Advanced-Algorithms/blob/master/tests/Advanced.Algorithms.Tests/DataStructures/Heap/FibonacciHeap_Tests.cs))
7878
- [X] Pairing heap ([implementation](https://github.com/justcoding121/Advanced-Algorithms/blob/master/src/Advanced.Algorithms/DataStructures/Heap/PairingHeap.cs) | [tests](https://github.com/justcoding121/Advanced-Algorithms/blob/master/tests/Advanced.Algorithms.Tests/DataStructures/Heap/PairingHeap_Tests.cs))
7979

8080
Note: It is observed that among the implementations here in practice, with the exclusion of UpdateKey (decrement/increment) operation regular Binary Heap & d-ary Heap outperforms other in theory superiors. Likely because it don't have pointer juggling overhead and hey arrays are faster!
@@ -175,11 +175,11 @@ TODO: implement trie compression.
175175
#### Shortest path
176176

177177
- [X] Bellman-Ford algorithm ([implementation](https://github.com/justcoding121/Advanced-Algorithms/blob/master/src/Advanced.Algorithms/Graph/ShortestPath/Bellman-Ford.cs) | [tests](https://github.com/justcoding121/Advanced-Algorithms/blob/master/tests/Advanced.Algorithms.Tests/Graph/ShortestPath/BellmanFord_Tests.cs))
178-
- [X] Dijikstra's algorithm ([implementation](https://github.com/justcoding121/Advanced-Algorithms/blob/master/src/Advanced.Algorithms/Graph/ShortestPath/Dijikstra.cs) | [tests](https://github.com/justcoding121/Advanced-Algorithms/blob/master/tests/Advanced.Algorithms.Tests/Graph/ShortestPath/Dijikstras_Tests.cs)) using Fibornacci heap.
178+
- [X] Dijikstra's algorithm ([implementation](https://github.com/justcoding121/Advanced-Algorithms/blob/master/src/Advanced.Algorithms/Graph/ShortestPath/Dijikstra.cs) | [tests](https://github.com/justcoding121/Advanced-Algorithms/blob/master/tests/Advanced.Algorithms.Tests/Graph/ShortestPath/Dijikstras_Tests.cs)) using Fibonacci heap.
179179
- [X] Floyd-Warshall algorithm ([implementation](https://github.com/justcoding121/Advanced-Algorithms/blob/master/src/Advanced.Algorithms/Graph/ShortestPath/Floyd-Warshall.cs) | [tests](https://github.com/justcoding121/Advanced-Algorithms/blob/master/tests/Advanced.Algorithms.Tests/Graph/ShortestPath/FloydWarshall_Tests.cs))
180180
- [X] Johnson's algorithm ([implementation](https://github.com/justcoding121/Advanced-Algorithms/blob/master/src/Advanced.Algorithms/Graph/ShortestPath/Johnsons.cs) | [tests](https://github.com/justcoding121/Advanced-Algorithms/blob/master/tests/Advanced.Algorithms.Tests/Graph/ShortestPath/Johnson_Tests.cs))
181181
- [X] Travelling salesman path ([implementation](https://github.com/justcoding121/Advanced-Algorithms/blob/master/src/Advanced.Algorithms/Graph/ShortestPath/TravellingSalesman.cs) | [tests](https://github.com/justcoding121/Advanced-Algorithms/blob/master/tests/Advanced.Algorithms.Tests/Graph/ShortestPath/TravellingSalesman_Tests.cs))
182-
- [X] A* search algorithm ([implementation](https://github.com/justcoding121/Advanced-Algorithms/blob/master/src/Advanced.Algorithms/Graph/ShortestPath/AStar.cs) | [tests](https://github.com/justcoding121/Advanced-Algorithms/blob/master/tests/Advanced.Algorithms.Tests/Graph/ShortestPath/AStar_Tests.cs)) using Fibornacci heap.
182+
- [X] A* search algorithm ([implementation](https://github.com/justcoding121/Advanced-Algorithms/blob/master/src/Advanced.Algorithms/Graph/ShortestPath/AStar.cs) | [tests](https://github.com/justcoding121/Advanced-Algorithms/blob/master/tests/Advanced.Algorithms.Tests/Graph/ShortestPath/AStar_Tests.cs)) using Fibonacci heap.
183183

184184
#### Matching
185185

‎src/Advanced.Algorithms/Compression/HuffmanCoding.cs

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
namespace Advanced.Algorithms.Compression
66
{
77
/// <summary>
8-
/// A huffman coding implementation using Fibornacci Min Heap.
8+
/// A huffman coding implementation using Fibonacci Min Heap.
99
/// </summary>
1010
public class HuffmanCoding<T>
1111
{

‎src/Advanced.Algorithms/DataStructures/Heap/FibornacciHeap.cs renamed to ‎src/Advanced.Algorithms/DataStructures/Heap/FibonacciHeap.cs

Lines changed: 19 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -8,22 +8,22 @@ namespace Advanced.Algorithms.DataStructures
88
/// <summary>
99
/// A fibornacci minMax heap implementation.
1010
/// </summary>
11-
public class FibornacciHeap<T> : IEnumerable<T> where T : IComparable
11+
public class FibonacciHeap<T> : IEnumerable<T> where T : IComparable
1212
{
1313
private readonly bool isMaxHeap;
1414
private readonly IComparer<T> comparer;
1515

1616
//holds the min/max node at any given time
17-
private FibornacciHeapNode<T> minMaxNode = null;
17+
private FibonacciHeapNode<T> minMaxNode = null;
1818

19-
private FibornacciHeapNode<T> heapForestHead;
19+
private FibonacciHeapNode<T> heapForestHead;
2020

21-
private Dictionary<T, List<FibornacciHeapNode<T>>> heapMapping
22-
= new Dictionary<T, List<FibornacciHeapNode<T>>>();
21+
private Dictionary<T, List<FibonacciHeapNode<T>>> heapMapping
22+
= new Dictionary<T, List<FibonacciHeapNode<T>>>();
2323

2424
public int Count { get; private set; }
2525

26-
public FibornacciHeap(SortDirection sortDirection = SortDirection.Ascending)
26+
public FibonacciHeap(SortDirection sortDirection = SortDirection.Ascending)
2727
{
2828
this.isMaxHeap = sortDirection == SortDirection.Descending;
2929
comparer = new CustomComparer<T>(sortDirection, Comparer<T>.Default);
@@ -34,7 +34,7 @@ public FibornacciHeap(SortDirection sortDirection = SortDirection.Ascending)
3434
/// </summary>
3535
public void Insert(T newItem)
3636
{
37-
var newNode = new FibornacciHeapNode<T>(newItem);
37+
var newNode = new FibonacciHeapNode<T>(newItem);
3838

3939
//return pointer to new Node
4040
mergeForests(newNode);
@@ -145,10 +145,10 @@ public void UpdateKey(T currentValue, T newValue)
145145
/// Unions this heap with another.
146146
/// Time complexity: O(1).
147147
/// </summary>
148-
public void Merge(FibornacciHeap<T> FibornacciHeap)
148+
public void Merge(FibonacciHeap<T> FibonacciHeap)
149149
{
150-
mergeForests(FibornacciHeap.heapForestHead);
151-
Count = Count + FibornacciHeap.Count;
150+
mergeForests(FibonacciHeap.heapForestHead);
151+
Count = Count + FibonacciHeap.Count;
152152
}
153153

154154
/// <summary>
@@ -177,7 +177,7 @@ private void Meld()
177177
}
178178

179179
//degree - node dictionary
180-
var mergeDictionary = new Dictionary<int, FibornacciHeapNode<T>>();
180+
var mergeDictionary = new Dictionary<int, FibonacciHeapNode<T>>();
181181

182182
var current = heapForestHead;
183183
minMaxNode = current;
@@ -270,7 +270,7 @@ private void Meld()
270270
/// <summary>
271271
/// Delete this node from Heap Tree and adds it to forest as a new tree
272272
/// </summary>
273-
private void cut(FibornacciHeapNode<T> node)
273+
private void cut(FibonacciHeapNode<T> node)
274274
{
275275
var parent = node.Parent;
276276

@@ -301,7 +301,7 @@ private void cut(FibornacciHeapNode<T> node)
301301
/// <summary>
302302
/// Merges the given fibornacci node list to current Forest
303303
/// </summary>
304-
private void mergeForests(FibornacciHeapNode<T> headPointer)
304+
private void mergeForests(FibonacciHeapNode<T> headPointer)
305305
{
306306
var current = headPointer;
307307
while (current != null)
@@ -313,7 +313,7 @@ private void mergeForests(FibornacciHeapNode<T> headPointer)
313313

314314
}
315315

316-
private void insertNode(ref FibornacciHeapNode<T> head, FibornacciHeapNode<T> newNode)
316+
private void insertNode(ref FibonacciHeapNode<T> head, FibonacciHeapNode<T> newNode)
317317
{
318318
newNode.Next = newNode.Previous = null;
319319

@@ -329,7 +329,7 @@ private void insertNode(ref FibornacciHeapNode<T> head, FibornacciHeapNode<T> ne
329329
head = newNode;
330330
}
331331

332-
private void deleteNode(ref FibornacciHeapNode<T> heapForestHead, FibornacciHeapNode<T> deletionNode)
332+
private void deleteNode(ref FibonacciHeapNode<T> heapForestHead, FibonacciHeapNode<T> deletionNode)
333333
{
334334
if (deletionNode == heapForestHead)
335335
{
@@ -355,26 +355,26 @@ private void deleteNode(ref FibornacciHeapNode<T> heapForestHead, FibornacciHeap
355355
deletionNode.Previous = null;
356356
}
357357

358-
private void addMapping(T newItem, FibornacciHeapNode<T> newNode)
358+
private void addMapping(T newItem, FibonacciHeapNode<T> newNode)
359359
{
360360
if (heapMapping.ContainsKey(newItem))
361361
{
362362
heapMapping[newItem].Add(newNode);
363363
}
364364
else
365365
{
366-
heapMapping[newItem] = new List<FibornacciHeapNode<T>>(new[] { newNode });
366+
heapMapping[newItem] = new List<FibonacciHeapNode<T>>(new[] { newNode });
367367
}
368368
}
369369

370-
private void updateNodeValue(T currentValue, T newValue, FibornacciHeapNode<T> node)
370+
private void updateNodeValue(T currentValue, T newValue, FibonacciHeapNode<T> node)
371371
{
372372
removeMapping(currentValue, node);
373373
node.Value = newValue;
374374
addMapping(newValue, node);
375375
}
376376

377-
private void removeMapping(T currentValue, FibornacciHeapNode<T> node)
377+
private void removeMapping(T currentValue, FibonacciHeapNode<T> node)
378378
{
379379
heapMapping[currentValue].Remove(node);
380380
if (heapMapping[currentValue].Count == 0)

‎src/Advanced.Algorithms/DataStructures/Heap/Shared/FibornacciHeapNode.cs

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -2,27 +2,27 @@
22

33
namespace Advanced.Algorithms.DataStructures
44
{
5-
internal class FibornacciHeapNode<T> : IComparable where T : IComparable
5+
internal class FibonacciHeapNode<T> : IComparable where T : IComparable
66
{
77
internal T Value { get; set; }
88

99
internal int Degree;
10-
internal FibornacciHeapNode<T> ChildrenHead { get; set; }
10+
internal FibonacciHeapNode<T> ChildrenHead { get; set; }
1111

12-
internal FibornacciHeapNode<T> Parent { get; set; }
12+
internal FibonacciHeapNode<T> Parent { get; set; }
1313
internal bool LostChild { get; set; }
1414

15-
internal FibornacciHeapNode<T> Previous;
16-
internal FibornacciHeapNode<T> Next;
15+
internal FibonacciHeapNode<T> Previous;
16+
internal FibonacciHeapNode<T> Next;
1717

18-
internal FibornacciHeapNode(T value)
18+
internal FibonacciHeapNode(T value)
1919
{
2020
Value = value;
2121
}
2222

2323
public int CompareTo(object obj)
2424
{
25-
return Value.CompareTo(((FibornacciHeapNode<T>) obj).Value);
25+
return Value.CompareTo(((FibonacciHeapNode<T>) obj).Value);
2626
}
2727
}
2828

‎src/Advanced.Algorithms/Graph/MinimumSpanningTree/Prims.cs

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -32,15 +32,15 @@ public List<MSTEdge<T, W>>
3232
/// Do DFS to pick smallest weight neighbour edges
3333
/// of current spanning tree one by one.
3434
/// </summary>
35-
/// <param name="spanTreeNeighbours"> Use Fibornacci Min Heap to pick smallest edge neighbour </param>
35+
/// <param name="spanTreeNeighbours"> Use Fibonacci Min Heap to pick smallest edge neighbour </param>
3636
/// <param name="spanTreeEdges">result MST edges</param>
3737
private void dfs(WeightedGraph<T, W> graph, WeightedGraphVertex<T, W> currentVertex,
3838
BHeap<MSTEdge<T, W>> spanTreeNeighbours, HashSet<T> spanTreeVertices,
3939
List<MSTEdge<T, W>> spanTreeEdges)
4040
{
4141
while (true)
4242
{
43-
//add all edges to Fibornacci Heap
43+
//add all edges to Fibonacci Heap
4444
//So that we can pick the min edge in next step
4545
foreach (var edge in currentVertex.Edges)
4646
{

‎src/Advanced.Algorithms/Graph/ShortestPath/AStar.cs

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
namespace Advanced.Algorithms.Graph
88
{
99
/// <summary>
10-
/// A* algorithm implementation using Fibornacci Heap.
10+
/// A* algorithm implementation using Fibonacci Heap.
1111
/// </summary>
1212
public class AStarShortestPath<T, W> where W : IComparable
1313
{
@@ -38,7 +38,7 @@ public ShortestPathResult<T, W> FindShortestPath(WeightedDiGraph<T, W> graph, T
3838
var parentMap = new Dictionary<T, T>();
3939

4040
//min heap to pick next closest vertex
41-
var minHeap = new FibornacciHeap<AStarWrap<T, W>>();
41+
var minHeap = new FibonacciHeap<AStarWrap<T, W>>();
4242
//keep references of heap Node for decrement key operation
4343
var heapMapping = new Dictionary<T, AStarWrap<T, W>>();
4444

@@ -167,7 +167,7 @@ public interface IAStarHeuristic<T, W> where W : IComparable
167167
W HueristicDistanceToTarget(T sourceVertex, T targetVertex);
168168
}
169169

170-
//Node for our Fibornacci heap
170+
//Node for our Fibonacci heap
171171
internal class AStarWrap<T, W> : IComparable where W : IComparable
172172
{
173173
private IAStarHeuristic<T, W> heuristic;

‎src/Advanced.Algorithms/Graph/ShortestPath/Dijikstra.cs

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
namespace Advanced.Algorithms.Graph
88
{
99
/// <summary>
10-
/// A dijikstra algorithm implementation using Fibornacci Heap.
10+
/// A dijikstra algorithm implementation using Fibonacci Heap.
1111
/// </summary>
1212
public class DijikstraShortestPath<T, W> where W : IComparable
1313
{
@@ -35,7 +35,7 @@ public ShortestPathResult<T, W> FindShortestPath(WeightedDiGraph<T, W> graph, T
3535
var parentMap = new Dictionary<T, T>();
3636

3737
//min heap to pick next closest vertex
38-
var minHeap = new FibornacciHeap<MinHeapWrap<T, W>>();
38+
var minHeap = new FibonacciHeap<MinHeapWrap<T, W>>();
3939
//keep references of heap Node for decrement key operation
4040
var heapMapping = new Dictionary<T, MinHeapWrap<T, W>>();
4141

‎tests/Advanced.Algorithms.Tests/Advanced.Algorithms.Tests.csproj

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -78,7 +78,7 @@
7878
<Compile Include="DataStructures\Heap\BHeap_Tests.cs" />
7979
<Compile Include="DataStructures\Heap\BinomialHeap_Tests.cs" />
8080
<Compile Include="DataStructures\Heap\D-aryHeap_Tests.cs" />
81-
<Compile Include="DataStructures\Heap\FibornacciHeap_Tests.cs" />
81+
<Compile Include="DataStructures\Heap\FibonacciHeap_Tests.cs" />
8282
<Compile Include="DataStructures\Heap\PairingHeap_Tests.cs" />
8383
<Compile Include="DataStructures\LinkedList\CircularLinkedList_Tests.cs" />
8484
<Compile Include="DataStructures\LinkedList\DoublyLinkedList_Tests.cs" />

‎tests/Advanced.Algorithms.Tests/DataStructures/Heap/FibornacciHeap_Tests.cs renamed to ‎tests/Advanced.Algorithms.Tests/DataStructures/Heap/FibonacciHeap_Tests.cs

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -7,15 +7,15 @@
77
namespace Advanced.Algorithms.Tests.DataStructures
88
{
99
[TestClass]
10-
public class FibornacciHeap_Tests
10+
public class FibonacciHeap_Tests
1111
{
1212

1313
[TestMethod]
14-
public void Min_FibornacciHeap_Test()
14+
public void Min_FibonacciHeap_Test()
1515
{
1616
int nodeCount = 1000 * 10;
1717

18-
var minHeap = new FibornacciHeap<int>();
18+
var minHeap = new FibonacciHeap<int>();
1919

2020
for (int i = 0; i <= nodeCount; i++)
2121
{
@@ -66,11 +66,11 @@ public void Min_FibornacciHeap_Test()
6666

6767

6868
[TestMethod]
69-
public void Max_FibornacciHeap_Test()
69+
public void Max_FibonacciHeap_Test()
7070
{
7171
int nodeCount = 1000 * 10;
7272

73-
var maxHeap = new FibornacciHeap<int>(SortDirection.Descending);
73+
var maxHeap = new FibonacciHeap<int>(SortDirection.Descending);
7474

7575
for (int i = 0; i <= nodeCount; i++)
7676
{

0 commit comments

Comments
 (0)