你可能会喜欢C5泛型集合库中的IntervalHeap。引用用户指南

类IntervalHeap<T>使用存储为对数组的间隔堆实现接口IPriorityQueue<T>。FindMin和 FindMax操作和索引器的get-访问器花费的时间为O(1)。DeleteMin, DeleteMax、Add和Update操作，以及索引器的集访问器，都需要时间 O(log n)。与普通优先级队列相比，间隔堆提供了两个最小优先级队列 同样效率的最大操作。

API非常简单

> var heap = new C5.IntervalHeap<int>();
> heap.Add(10);
> heap.Add(5);
> heap.FindMin();
5

从Nuget https://www.nuget.org/packages/C5或GitHub https://github.com/sestoft/C5/安装

下面的PriorityQueue实现使用了System库中的SortedSet。

using System;
using System.Collections.Generic;

namespace CDiggins
{
    interface IPriorityQueue<T, K> where K : IComparable<K>
    {
        bool Empty { get; }
        void Enqueue(T x, K key);
        void Dequeue();
        T Top { get; }
    }

    class PriorityQueue<T, K> : IPriorityQueue<T, K> where K : IComparable<K>
    {
        SortedSet<Tuple<T, K>> set;

        class Comparer : IComparer<Tuple<T, K>> {
            public int Compare(Tuple<T, K> x, Tuple<T, K> y) {
                return x.Item2.CompareTo(y.Item2);
            }
        }

        PriorityQueue() { set = new SortedSet<Tuple<T, K>>(new Comparer()); }
        public bool Empty { get { return set.Count == 0;  } }
        public void Enqueue(T x, K key) { set.Add(Tuple.Create(x, key)); }
        public void Dequeue() { set.Remove(set.Max); }
        public T Top { get { return set.Max.Item1; } }
    }
}

下面是来自NGenerics团队的另一个实现:

NGenerics PriorityQueue

我最近也遇到了同样的问题，最后为此创建了一个NuGet包。

这实现了一个标准的基于堆的优先级队列。它还具有BCL集合的所有常见的优点:ICollection<T>和IReadOnlyCollection<T>实现，自定义IComparer<T>支持，指定初始容量的能力，以及使集合更容易在调试器中使用的DebuggerTypeProxy。

还有一个内联版本的包，它只安装一个.cs文件到你的项目中(如果你想避免外部可见的依赖关系，这很有用)。

更多信息请访问github页面。

下面是我对.NET堆的尝试

public abstract class Heap<T> : IEnumerable<T>
{
    private const int InitialCapacity = 0;
    private const int GrowFactor = 2;
    private const int MinGrow = 1;

    private int _capacity = InitialCapacity;
    private T[] _heap = new T[InitialCapacity];
    private int _tail = 0;

    public int Count { get { return _tail; } }
    public int Capacity { get { return _capacity; } }

    protected Comparer<T> Comparer { get; private set; }
    protected abstract bool Dominates(T x, T y);

    protected Heap() : this(Comparer<T>.Default)
    {
    }

    protected Heap(Comparer<T> comparer) : this(Enumerable.Empty<T>(), comparer)
    {
    }

    protected Heap(IEnumerable<T> collection)
        : this(collection, Comparer<T>.Default)
    {
    }

    protected Heap(IEnumerable<T> collection, Comparer<T> comparer)
    {
        if (collection == null) throw new ArgumentNullException("collection");
        if (comparer == null) throw new ArgumentNullException("comparer");

        Comparer = comparer;

        foreach (var item in collection)
        {
            if (Count == Capacity)
                Grow();

            _heap[_tail++] = item;
        }

        for (int i = Parent(_tail - 1); i >= 0; i--)
            BubbleDown(i);
    }

    public void Add(T item)
    {
        if (Count == Capacity)
            Grow();

        _heap[_tail++] = item;
        BubbleUp(_tail - 1);
    }

    private void BubbleUp(int i)
    {
        if (i == 0 || Dominates(_heap[Parent(i)], _heap[i])) 
            return; //correct domination (or root)

        Swap(i, Parent(i));
        BubbleUp(Parent(i));
    }

    public T GetMin()
    {
        if (Count == 0) throw new InvalidOperationException("Heap is empty");
        return _heap[0];
    }

    public T ExtractDominating()
    {
        if (Count == 0) throw new InvalidOperationException("Heap is empty");
        T ret = _heap[0];
        _tail--;
        Swap(_tail, 0);
        BubbleDown(0);
        return ret;
    }

    private void BubbleDown(int i)
    {
        int dominatingNode = Dominating(i);
        if (dominatingNode == i) return;
        Swap(i, dominatingNode);
        BubbleDown(dominatingNode);
    }

    private int Dominating(int i)
    {
        int dominatingNode = i;
        dominatingNode = GetDominating(YoungChild(i), dominatingNode);
        dominatingNode = GetDominating(OldChild(i), dominatingNode);

        return dominatingNode;
    }

    private int GetDominating(int newNode, int dominatingNode)
    {
        if (newNode < _tail && !Dominates(_heap[dominatingNode], _heap[newNode]))
            return newNode;
        else
            return dominatingNode;
    }

    private void Swap(int i, int j)
    {
        T tmp = _heap[i];
        _heap[i] = _heap[j];
        _heap[j] = tmp;
    }

    private static int Parent(int i)
    {
        return (i + 1)/2 - 1;
    }

    private static int YoungChild(int i)
    {
        return (i + 1)*2 - 1;
    }

    private static int OldChild(int i)
    {
        return YoungChild(i) + 1;
    }

    private void Grow()
    {
        int newCapacity = _capacity*GrowFactor + MinGrow;
        var newHeap = new T[newCapacity];
        Array.Copy(_heap, newHeap, _capacity);
        _heap = newHeap;
        _capacity = newCapacity;
    }

    public IEnumerator<T> GetEnumerator()
    {
        return _heap.Take(Count).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

public class MaxHeap<T> : Heap<T>
{
    public MaxHeap()
        : this(Comparer<T>.Default)
    {
    }

    public MaxHeap(Comparer<T> comparer)
        : base(comparer)
    {
    }

    public MaxHeap(IEnumerable<T> collection, Comparer<T> comparer)
        : base(collection, comparer)
    {
    }

    public MaxHeap(IEnumerable<T> collection) : base(collection)
    {
    }

    protected override bool Dominates(T x, T y)
    {
        return Comparer.Compare(x, y) >= 0;
    }
}

public class MinHeap<T> : Heap<T>
{
    public MinHeap()
        : this(Comparer<T>.Default)
    {
    }

    public MinHeap(Comparer<T> comparer)
        : base(comparer)
    {
    }

    public MinHeap(IEnumerable<T> collection) : base(collection)
    {
    }

    public MinHeap(IEnumerable<T> collection, Comparer<T> comparer)
        : base(collection, comparer)
    {
    }

    protected override bool Dominates(T x, T y)
    {
        return Comparer.Compare(x, y) <= 0;
    }
}

一些测试:

[TestClass]
public class HeapTests
{
    [TestMethod]
    public void TestHeapBySorting()
    {
        var minHeap = new MinHeap<int>(new[] {9, 8, 4, 1, 6, 2, 7, 4, 1, 2});
        AssertHeapSort(minHeap, minHeap.OrderBy(i => i).ToArray());

        minHeap = new MinHeap<int> { 7, 5, 1, 6, 3, 2, 4, 1, 2, 1, 3, 4, 7 };
        AssertHeapSort(minHeap, minHeap.OrderBy(i => i).ToArray());

        var maxHeap = new MaxHeap<int>(new[] {1, 5, 3, 2, 7, 56, 3, 1, 23, 5, 2, 1});
        AssertHeapSort(maxHeap, maxHeap.OrderBy(d => -d).ToArray());

        maxHeap = new MaxHeap<int> {2, 6, 1, 3, 56, 1, 4, 7, 8, 23, 4, 5, 7, 34, 1, 4};
        AssertHeapSort(maxHeap, maxHeap.OrderBy(d => -d).ToArray());
    }

    private static void AssertHeapSort(Heap<int> heap, IEnumerable<int> expected)
    {
        var sorted = new List<int>();
        while (heap.Count > 0)
            sorted.Add(heap.ExtractDominating());

        Assert.IsTrue(sorted.SequenceEqual(expected));
    }
}

我在Julian Bucknall的博客(http://www.boyet.com/Articles/PriorityQueueCSharp3.html)上找到了一个

我们稍微修改了一下，以便队列中优先级低的项目最终会随着时间的推移“上升”到顶部，这样它们就不会挨饿了。