# Fibonacci heap implementation

Posted on

Problem

I’d like this reviewed.

``````public sealed class FibonacciHeap<TKey, TValue>
{
readonly List<Node> _root = new List<Node>();
int _count;
Node _min;

public void Push(TKey key, TValue value)
{
Insert(new Node {
Key = key,
Value = value
});
}

public KeyValuePair<TKey, TValue> Peek()
{
if (_min == null)
throw new InvalidOperationException();
return new KeyValuePair<TKey,TValue>(_min.Key, _min.Value);
}

public KeyValuePair<TKey, TValue> Pop()
{
if (_min == null)
throw new InvalidOperationException();
var min = ExtractMin();
return new KeyValuePair<TKey,TValue>(min.Key, min.Value);
}

void Insert(Node node)
{
_count++;
if (_min == null)
{
_min = node;
}
else if (Comparer<TKey>.Default.Compare(node.Key, _min.Key) < 0)
{
_min = node;
}
}

Node ExtractMin()
{
var result = _min;
if (result == null)
return null;
foreach (var child in result.Children)
{
child.Parent = null;
}
_root.Remove(result);
if (_root.Count == 0)
{
_min = null;
}
else
{
_min = _root[0];
Consolidate();
}
_count--;
return result;
}

void Consolidate()
{
var a = new Node[UpperBound()];
for (int i = 0; i < _root.Count; i++)
{
var x = _root[i];
var d = x.Children.Count;
while (true)
{
var y = a[d];
if (y == null)
break;
if (Comparer<TKey>.Default.Compare(x.Key, y.Key) > 0)
{
var t = x;
x = y;
y = t;
}
_root.Remove(y);
i--;
y.Mark = false;
a[d] = null;
d++;
}
a[d] = x;
}
_min = null;
for (int i = 0; i < a.Length; i++)
{
var n = a[i];
if (n == null)
continue;
if (_min == null)
{
_root.Clear();
_min = n;
}
else
{
if (Comparer<TKey>.Default.Compare(n.Key, _min.Key) < 0)
{
_min = n;
}
}
}
}

int UpperBound()
{
return (int)Math.Floor(Math.Log(_count, (1.0 + Math.Sqrt(5)) / 2.0)) + 1;
}

class Node
{
public TKey Key;
public TValue Value;
public Node Parent;
public List<Node> Children = new List<Node>();
public bool Mark;

{
child.Parent = this;
}

public override string ToString()
{
return string.Format("({0},{1})", Key, Value);
}
}
}
``````

Solution

Disclaimer: I will not address the actual FibonacciHeap itself, just the c# code.

I explicitly write the `private` keyword on those methods and properties, so they are indented roughly the same as the `public` ones. A matter of preference, I guess.

These `_name` variables are odd, I suggest using the de facto standard of PascalCase.

`_count` seems to be a duplication of `Root.count`. I would remove it.
However, ExtractMin adds items to the Root and does not increment count! This seems like a bug, but perhaps it’s not. If it is, it is a strong justification for removing `_count`; if not, it could use a quick comment there to signal why `_count` is not updated.

Because I like my variables very strongly typed, I don’t like `var`. I changed most of its uses to an explicit type.

You can if-chain if-elses better if you do not use parenthesis around the else that takes an if inside:

``````if (Min == null) {
Root.Clear();
Min = item;
} else if (Comparer<TKey>.Default.Compare(item.Key, Min.Key) < 0) {
Min = item;
} // else if() { } else if() { } etc
``````

A `Node` does not seem to make sense without a `Key` and a `Value`, so I would add a constructor that takes those two.

You overrode `Node.ToString`. I assume that was for debugging purposes? I would use the `DebuggerDisplay` attribute in the class, instead.

Here is a proposal of reviewed code, with some highlights in comments:

``````public sealed class FibonacciHeap<TKey, TValue>
{
private readonly List<Node> Root = new List<Node>();
// TODO: is this not a duplication of Root.Count? Remove it.
private int _count;
private Node Min;

public void Push(TKey key, TValue value)
{
Insert(new Node(key, value));
}

public KeyValuePair<TKey, TValue> Peek()
{
if (Min == null)
throw new InvalidOperationException();
return new KeyValuePair<TKey, TValue>(Min.Key, Min.Value);
}

public KeyValuePair<TKey, TValue> Pop()
{
if (Min == null)
throw new InvalidOperationException();
var min = ExtractMin();
return new KeyValuePair<TKey, TValue>(min.Key, min.Value);
}

private void Insert(Node node)
{
_count++;
if (Min == null)
{
Min = node;
} else if (Comparer<TKey>.Default.Compare(node.Key, Min.Key) < 0)
{
Min = node;
}
}

private Node ExtractMin()
{
var result = Min;
if (result == null)
return null;
foreach (var child in result.Children)
{
child.Parent = null;
// TODO: shouldn't _count be updated?? Same in Consolidate();
}
Root.Remove(result);
if (Root.Count == 0)
{
Min = null;
} else
{
Min = Root[0];
Consolidate();
}
_count--;
return result;
}

// Here be FibonacciHeap dragons.
private void Consolidate()
{
var unlabeledBag = new Node[UpperBound()];
for (int i = 0; i < Root.Count; i++)
{
Node item = Root[i];
int itemChildren = item.Children.Count;
while (true)
{
Node child = unlabeledBag[itemChildren];
if (child == null)
break;
if (Comparer<TKey>.Default.Compare(item.Key, child.Key) > 0)
{
var swap = item;
item = child;
child = swap;
}
Root.Remove(child);
i--;
child.Mark = false;
unlabeledBag[itemChildren] = null;
itemChildren++;
}
unlabeledBag[itemChildren] = item;
}
Min = null;
for (int i = 0; i < unlabeledBag.Length; i++)
{
var item = unlabeledBag[i];
if (item == null)
continue;
if (Min == null)
{
Root.Clear();
Min = item;
} else if (Comparer<TKey>.Default.Compare(item.Key, Min.Key) < 0)
{
Min = item;
}
}
}

private int UpperBound()
{
// Here be dragons.
// Also, if _count is NOT Root.Count, it ought to at least have a more meaningful name.
double magicValue = Math.Log(_count, (1.0 + Math.Sqrt(5)) / 2.0);
return (int)Math.Floor(magicValue) + 1;
}

[DebuggerDisplay("{Key}, {Value}")]
private class Node
{
public TKey Key;
public TValue Value;
public Node Parent;
public List<Node> Children = new List<Node>();
public bool Mark;

public Node(TKey key, TValue value)
{
Key = key;
Value = value;
}