<h2>AlgoKit</h2>

<p>I wrote an open source library called <a href="https://github.com/pgolebiowski/algo-kit" rel="noreferrer">AlgoKit</a>, available via <a href="https://www.nuget.org/packages/AlgoKit" rel="noreferrer">NuGet</a>. It contains:</p>

<ul>
<li><strong>Implicit d-ary heaps</strong> (ArrayHeap),</li>
<li><strong>Binomial heaps</strong>,</li>
<li><strong>Pairing heaps</strong>.</li>
</ul>

<p>The code has been extensively tested. I definitely recommend you to give it a try.</p>

<h2>Example</h2>

<pre><code>var comparer = Comparer&lt;int&gt;.Default;
var heap = new PairingHeap&lt;int, string&gt;(comparer);

heap.Add(3, "your");
heap.Add(5, "of");
heap.Add(7, "disturbing.");
heap.Add(2, "find");
heap.Add(1, "I");
heap.Add(6, "faith");
heap.Add(4, "lack");

while (!heap.IsEmpty)
    Console.WriteLine(heap.Pop().Value);
</code></pre>

<h2>Why those three heaps?</h2>

<p>The optimal choice of implementation is strongly input-dependent — as Larkin, Sen, and Tarjan show in <em>A back-to-basics empirical study of priority queues</em>, <a href="https://arxiv.org/abs/1403.0252v1" rel="noreferrer">arXiv:1403.0252v1 [cs.DS]</a>. They tested implicit d-ary heaps, pairing heaps, Fibonacci heaps, binomial heaps, explicit d-ary heaps, rank-pairing heaps, quake heaps, violation heaps, rank-relaxed weak heaps, and strict Fibonacci heaps.</p>

<p>AlgoKit features three types of heaps that appeared to be most efficient among those tested.</p>

<h2>Hint on choice</h2>

<p>For a relatively small number of elements, you would likely be interested in using implicit heaps, especially quaternary heaps (implicit 4-ary). In case of operating on larger heap sizes, amortized structures like binomial heaps and pairing heaps should perform better.</p>
Priority queue in .Net
<p>I am looking for a .NET implementation of a priority queue or heap data structure</p>

<blockquote>
  <p>Priority queues are data structures that provide more flexibility than simple sorting, because they allow new elements to enter a system at arbitrary intervals. It is much more cost-effective to insert a new job into a priority queue than to re-sort everything on each such arrival.</p>
  
  <p>The basic priority queue supports three primary operations:</p>
  
  <ul>
  <li>Insert(Q,x). Given an item x with key k, insert it into the priority queue Q.</li>
  <li>Find-Minimum(Q). Return a pointer to the item
  whose key value is smaller than any other key in the priority queue
  Q.</li>
  <li>Delete-Minimum(Q). Remove the item from the priority queue Q whose key is minimum</li>
  </ul>
</blockquote>

<p>Unless I am looking in the wrong place, there isn't one in the framework. Is anyone aware of a good one, or should I roll my own?</p>