Fibonacci heap implementation I'd like this reviewed.

public sealed class FibonacciHeap&lt;TKey, TValue&gt;
{
    readonly List&lt;Node&gt; _root = new List&lt;Node&gt;();
    int _count;
    Node _min;

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

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

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

    void Insert(Node node)
    {
        _count++;
        _root.Add(node);
        if (_min == null)
        {
            _min = node;
        }
        else if (Comparer&lt;TKey&gt;.Default.Compare(node.Key, _min.Key) &lt; 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 &lt; _root.Count; i++)
        {
            var x = _root[i];
            var d = x.Children.Count;
            while (true)
            {   
                var y = a[d];
                if (y == null)
                    break;                  
                if (Comparer&lt;TKey&gt;.Default.Compare(x.Key, y.Key) &gt; 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 &lt; a.Length; i++)
        {
            var n = a[i];
            if (n == null)
                continue;
            if (_min == null)
            {
                _root.Clear();
                _min = n;
            }
            else
            {
                if (Comparer&lt;TKey&gt;.Default.Compare(n.Key, _min.Key) &lt; 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&lt;Node&gt; Children = new List&lt;Node&gt;();
        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);
        }
    }
}
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&lt;TKey&gt;.Default.Compare(item.Key, Min.Key) &lt; 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&lt;TKey, TValue&gt;
{
    private readonly List&lt;Node&gt; Root = new List&lt;Node&gt;();
    // 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&lt;TKey, TValue&gt; Peek()
    {
        if (Min == null)
            throw new InvalidOperationException();
        return new KeyValuePair&lt;TKey, TValue&gt;(Min.Key, Min.Value);
    }

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

    private void Insert(Node node)
    {
        _count++;
        Root.Add(node);
        if (Min == null)
        {
            Min = node;
        } else if (Comparer&lt;TKey&gt;.Default.Compare(node.Key, Min.Key) &lt; 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 &lt; Root.Count; i++)
        {
            Node item = Root[i];
            int itemChildren = item.Children.Count;
            while (true)
            {
                Node child = unlabeledBag[itemChildren];
                if (child == null)
                    break;
                if (Comparer&lt;TKey&gt;.Default.Compare(item.Key, child.Key) &gt; 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 &lt; unlabeledBag.Length; i++)
        {
            var item = unlabeledBag[i];
            if (item == null)
                continue;
            if (Min == null)
            {
                Root.Clear();
                Min = item;
            } else if (Comparer&lt;TKey&gt;.Default.Compare(item.Key, Min.Key) &lt; 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&lt;Node&gt; Children = new List&lt;Node&gt;();
        public bool Mark;

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

        public void AddChild(Node child)
        {
            child.Parent = this;
            Children.Add(child);
        }
    }
}