BinomialHeap.cs

using System;
using System.Linq;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Collections.Generic;

namespace ConsoleApplication
{
    public static class MoreLinq
    {
        public static TSource MinBy<TSource>(
                this IEnumerable<TSource> source,
                Func<TSource, IComparable> projectionToComparable
            ) 
        {
            using (var e = source.GetEnumerator()) {
                if (!e.MoveNext()) {
                    throw new InvalidOperationException("Sequence is empty.");
                }
                TSource min = e.Current;
                IComparable minProjection = projectionToComparable(e.Current);
                while (e.MoveNext()) {
                    IComparable currentProjection = projectionToComparable(e.Current);
                    if (currentProjection.CompareTo(minProjection) < 0) {
                        min = e.Current;
                        minProjection = currentProjection;
                    }
                }
                return min;                
            }
        }       
    }

    public struct Node<T> where T : IComparable
    {
        public Node(T element, int rank, ImmutableList<Node<T>> children)
        {
            Element = element;
            Rank = rank;
            Children = children;
        }

        public T Element { get; }

        public int Rank { get; }

        public ImmutableList<Node<T>> Children { get; }
    }        
    
    public struct BinomialHeap<T> where T : IComparable
    {
        public BinomialHeap(ImmutableList<Node<T>> trees)
        {
            this.Trees = trees;
        }

        private ImmutableList<Node<T>> Trees { get; }

        public static BinomialHeap<T> Empty
        {
            get
            {
                return new BinomialHeap<T>(ImmutableList<Node<T>>.Empty);
            }
        }

        public BinomialHeap<T> Insert(T elem)
        {
            var tree = new Node<T>(elem, 0, ImmutableList<Node<T>>.Empty);
            var newTrees = InsertTree(tree, this.Trees);
            return new BinomialHeap<T>(newTrees);
        }

        private static ImmutableList<Node<T>> InsertTree(Node<T> tree, ImmutableList<Node<T>> trees)
        {
            if (trees.IsEmpty) 
            {
                return ImmutableList<Node<T>>.Empty.Add(tree);
            }

            var head = trees.First();
            if (tree.Rank < head.Rank)
            {
                return trees.Insert(0, tree);
            } 
            else
            {
                return InsertTree(Link(tree, head), trees.RemoveAt(0));
            }
        }

        private static Node<T> Link(Node<T> t1, Node<T> t2)
        {
            Debug.Assert(t1.Rank == t2.Rank);
            if (t1.Element.CompareTo(t2.Element) < 0)
            {
                return new Node<T>(t1.Element, t1.Rank + 1, t1.Children.Insert(0, t2));
            }
            else            
            {
                return new Node<T>(t2.Element, t1.Rank + 1, t2.Children.Insert(0, t1));               
            }
        }

        
        public BinomialHeap<T> DeleteMin()
        {
            var minTree = this.Trees.AsEnumerable().MinBy(t => t.Element);
            var newTrees = this.Trees.Remove(minTree);    
            var root = Merge(minTree.Children.Reverse(), newTrees);
            return new BinomialHeap<T>(root);
        }

        private ImmutableList<Node<T>> Merge(ImmutableList<Node<T>> ts1, ImmutableList<Node<T>> ts2)
        {
            if (ts1.Count == 0)
            {
                return ts2;
            }

            if (ts2.Count == 0)
            {
                return ts1;
            }
            
            if (ts1.First().Rank < ts2.First().Rank)
            {
                return Merge(ts1.RemoveAt(0), ts2).Insert(0,ts1.First());
            }
            else if (ts2.First().Rank < ts1.First().Rank)
            {
                return Merge(ts2.RemoveAt(0), ts1).Insert(0,ts2.First());
            }        
            else
            {
                var linked = Link(ts1.First(), ts2.First());
                return InsertTree(linked, ts1.RemoveAt(0).AddRange(ts2.RemoveAt(0)));
            }
        }

        public T FindMin()
        {            
            return this.Trees.Min(t => t.Element);
        }
    }

    public class Program
    {
        public static void Main(string[] args)
        {
            var sampleHeap = BinomialHeap<int>.Empty;
            var ints = new int[] {1,30,20,3,17,-6,63,66,2,45};
            foreach(var i in ints)
            {
                sampleHeap = sampleHeap.Insert(i);
            }

            var min = sampleHeap.FindMin();
            var min2 = sampleHeap.DeleteMin().FindMin();
            var min3 = sampleHeap.DeleteMin().DeleteMin().FindMin();
            Console.WriteLine(min);
        }
    }
}