2
\$\begingroup\$

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);
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – ANeves Mar 16 '12 at 19:04
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – ChaosPandion Mar 16 '12 at 19:07
  • \$\begingroup\$ @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. \$\endgroup\$ – ChaosPandion Mar 16 '12 at 19:13
  • \$\begingroup\$ 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. \$\endgroup\$ – Leonid Mar 18 '12 at 2:43
  • \$\begingroup\$ @Leonid - Write up an answer. The suggestion about the if is pretty good. I must have originally had some more code in there. \$\endgroup\$ – ChaosPandion Mar 18 '12 at 3:11
1
\$\begingroup\$

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);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Prefer _camelCase for private fields. This is the OOTB standard Resharper enforces and indicates that the field is privately scoped to this instance. So, for example, extra care should be taken in case it's a backing field for a property. Using PascalCase could conflict with property refactoring, and plain camelCase you'd need to check if it's a local variable. \$\endgroup\$ – jzx May 6 '14 at 21:52
  • 1
    \$\begingroup\$ I really don't like those underscores in a language that is otherwise free of them. But unfortunately I have no alternative, so that is also the convention I use these days. \$\endgroup\$ – ANeves May 7 '14 at 13:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.