Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment