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++;
_root.Add(node);
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.Add(child);
}
_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--;
x.AddChild(y);
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;
}
}
_root.Add(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;
public void AddChild(Node child)
{
child.Parent = this;
Children.Add(child);
}
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++;
Root.Add(node);
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.Add(child);
}
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--;
item.AddChild(child);
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;
}
Root.Add(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;
}
public void AddChild(Node child)
{
child.Parent = this;
Children.Add(child);
}
}
}