here is code for the "Soft Heap"

[not_a_commie]

Here is some code for the Soft Heap, taken directly from the original
paper on the subject with a little help from manish_gupta.
Unfortunately, it's about half as fast as a basic binary heap simply
because of memory allocation. In fact, my profiler says that 90% of
the time in this sucker is memory allocation. Can anybody devise a way
to cut down on the number of "news" in this? I need to insert a few
million elements and remove a tenth of that. I don't really want to do
several million memory allocations. Thanks for your time.

using System;

namespace HeapTests
{
public class ILCell<Twhere T : IComparable<T>, IInfinitable
{
public ILCell<TNext = null;
public T Key;
}

public class Node<Twhere T : IComparable<T>, IInfinitable
{
public T Key;
public int Rank = 0;
public Node<TNext = null, Child = null;
public ILCell<TIL = null, ILTail = null;
}

public class Head<Twhere T : IComparable<T>, IInfinitable
{
public Node<TQueue = null;
public Head<TNext = null, Previous = null, Suffix = null;
public int Rank = int.MaxValue;
}

public interface IInfinitable
{
bool Infinite { get; set; }
}

public class SoftHeap<Twhere T : IComparable<T>, IInfinitable
{
private readonly Head<T_header = new Head<T>(), _tail = new
Head<T>();
private readonly int _r;
public SoftHeap(int allowCorruptOne In)
{
_r = 2 + 2 * (int)Math.Ceili ng(Math.Log(all owCorruptOneIn) );
_header.Next = _tail;
_tail.Previous = _header;
}

private int _count = 0;
public int Count { get { return _count; } }

public void Insert(T key)
{
ILCell<Tl = new ILCell<T>();
l.Key = key;
Node<Tq = new Node<T>();
q.Key = key;
q.IL = l;
q.ILTail = l;
Meld(q);
_count++;
}

private void Meld(Node<Tq)
{
Head<Th, prevhead, tohead = _header.Next;
Node<Ttop;
while (q.Rank tohead.Rank)
tohead = tohead.Next;
prevhead = tohead.Previous ;
while (q.Rank == tohead.Rank)
{
Node<Tbottom;
if (tohead.Queue.K ey.CompareTo(q. Key) 0)
{
top = q;
bottom = tohead.Queue;
}
else
{
top = tohead.Queue;
bottom = q;
}
q = new Node<T>();
q.Key = top.Key;
q.Rank = top.Rank + 1;
q.Child = bottom;
q.Next = top;
q.IL = top.IL;
q.ILTail = top.ILTail;
tohead = tohead.Next;
}
if (prevhead == tohead.Previous )
h = new Head<T>();
else
h = prevhead.Next;
h.Queue = q;
h.Rank = q.Rank;
h.Previous = prevhead;
h.Next = tohead;
prevhead.Next = h;
tohead.Previous = h;
FixMinList(h);
}
private void FixMinList(Head <Th)
{
Head<Ttmpmin;
if (h.Next == _tail) tmpmin = h;
else tmpmin = h.Next.Suffix;
while (h != _header)
{
if (h.Queue.Key.Co mpareTo(tmpmin. Queue.Key) < 0)
{
tmpmin = h;
}
h.Suffix = tmpmin;
h = h.Previous;
}
}

public T DeleteMin()
{
if (_count == 0)
return default(T);
Node<Ttmp;
Head<Th = _header.Next.Su ffix;
if (h == null)
return default(T);
while (h.Queue.IL == null)
{
tmp = h.Queue;
int childcount = 0;
while (tmp.Next != null)
{
tmp = tmp.Next;
childcount++;
}
if (childcount < h.Rank/2)
{
h.Previous.Next = h.Next;
h.Next.Previous = h.Previous;
FixMinList(h.Pr evious);
tmp = h.Queue;
while (tmp.Next != null)
{
Meld(tmp.Child) ;
tmp = tmp.Next;
}
}
else
{
h.Queue = Sift(h.Queue);
if (h.Queue.Key.In finite)
{
h.Previous.Next = h.Next;
h.Next.Previous = h.Previous;
h = h.Previous;
}
FixMinList(h);
}
h = _header.Next.Su ffix;
if(h == null || h.Queue == null)
return default(T);
}
T min = h.Queue.IL.Key;
h.Queue.IL = h.Queue.IL.Next ;
if (h.Queue.IL == null)
h.Queue.ILTail = null;
_count--;
return min;
}

private Node<TSift(Node <Tv)
{
Node<Ttmp;
v.IL = null;
v.ILTail = null;
if(v.Next == null && v.Child == null)
{
v.Key.Infinite = true;
return v;
}
v.Next = Sift(v.Next);

if (v.Next.Key.Com pareTo(v.Child. Key) 0)
{
tmp = v.Child;
v.Child = v.Next;
v.Next = tmp;
}

v.IL = v.Next.IL;
v.ILTail = v.Next.ILTail;
v.Key = v.Next.Key;

if (v.Rank _r && (v.Rank % 2 == 1 || v.Child.Rank < v.Rank - 1))
{
v.Next = Sift(v.Next);
if (v.Next.Key.Com pareTo(v.Child. Key) 0)
{
tmp = v.Child;
v.Child = v.Next;
v.Next = tmp;
}
if (!v.Next.Key.In finite && v.Next.IL != null)
{
v.Next.ILTail.N ext = v.IL;
v.IL = v.Next.IL;
if (v.ILTail == null)
v.ILTail = v.Next.ILTail;
v.Key = v.Next.Key;
}
}
if (v.Child.Key.In finite)
{
if (v.Next.Key.Inf inite)
{
v.Child = null;
v.Next = null;
}
else
{
v.Child = v.Next.Child;
v.Next = v.Next.Next;
}
}
return v;
}
}
}