# Fibonacci heap implementation

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);
}
}
}

• a, x, d, y, t: I think I would really enjoy reading your code if not for these random variable names. i, n are proper one-letter variable names because they are obvious, but the others are just confusing. Mar 16, 2012 at 19:04
• @ANeves - Why don't you make your opinion more prominent by writing an answer? Keep in mind that this code has no dependencies so you can easily try it out. Mar 16, 2012 at 19:07
• @ANeves - By the way I would consider this a rough draft. Typically if I cannot quickly come up with a useful name I'll use a poor name and try again on a second pass. Mar 16, 2012 at 19:13
• Disclaimer: I gave it a superficial read without having VS2010 by my side. I second variable names, I would run StyleCop on this and listen to suggestions of it. I would rewrite one else { if as elseif. I personally would make the whole body of public void Push(TKey key, TValue value) a one-liner. Mar 18, 2012 at 2:43
• @Leonid - Write up an answer. The suggestion about the if is pretty good. I must have originally had some more code in there. Mar 18, 2012 at 3:11

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;
}