.Net 中的优先级队列实现

我喜欢使用PowerCollections中的OrderedBag和OrderedSet类作为优先队列。

在Java Collections框架中的Java实现(Java .util. priorityqueue)上使用Java到c#的转换器，或者更智能地使用算法和核心代码，并将其插入到您自己制作的c#类中，该类遵循c# Collections框架用于队列的API，或者至少是Collections。

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

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

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

IntervalHeap<T>类使用存储为对数组的间隔堆实现接口IPriorityQueue<T>。FindMin和 FindMax操作，以及索引器的get-accessor，花费时间O(1)。DeleteMin, DeleteMax，添加和更新操作，以及索引器的集访问器，需要时间 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/安装

它是通用的，基于堆数据结构

这是我刚刚写的一个，也许它没有那么优化(只是使用了一个排序字典)，但很容易理解。 你可以插入不同类型的对象，所以没有泛型队列

using System;
using System.Diagnostics;
using System.Collections;
using System.Collections.Generic;


namespace PrioQueue
{
public class PrioQueue
{
int total_size;
SortedDictionary<int, Queue> storage;


public PrioQueue ()
{
this.storage = new SortedDictionary<int, Queue> ();
this.total_size = 0;
}


public bool IsEmpty ()
{
return (total_size == 0);
}


public object Dequeue ()
{
if (IsEmpty ()) {
throw new Exception ("Please check that priorityQueue is not empty before dequeing");
} else
foreach (Queue q in storage.Values) {
// we use a sorted dictionary
if (q.Count > 0) {
total_size--;
return q.Dequeue ();
}
}


Debug.Assert(false,"not supposed to reach here. problem with changing total_size");


return null; // not supposed to reach here.
}


// same as above, except for peek.


public object Peek ()
{
if (IsEmpty ())
throw new Exception ("Please check that priorityQueue is not empty before peeking");
else
foreach (Queue q in storage.Values) {
if (q.Count > 0)
return q.Peek ();
}


Debug.Assert(false,"not supposed to reach here. problem with changing total_size");


return null; // not supposed to reach here.
}


public object Dequeue (int prio)
{
total_size--;
return storage[prio].Dequeue ();
}


public void Enqueue (object item, int prio)
{
if (!storage.ContainsKey (prio)) {
storage.Add (prio, new Queue ());
}
storage[prio].Enqueue (item);
total_size++;


}
}
}

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

NGenerics PriorityQueue

下面是我对.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));
}
}

下面的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; } }
}
}

class PriorityQueue<T>
{
IComparer<T> comparer;
T[] heap;
public int Count { get; private set; }
public PriorityQueue() : this(null) { }
public PriorityQueue(int capacity) : this(capacity, null) { }
public PriorityQueue(IComparer<T> comparer) : this(16, comparer) { }
public PriorityQueue(int capacity, IComparer<T> comparer)
{
this.comparer = (comparer == null) ? Comparer<T>.Default : comparer;
this.heap = new T[capacity];
}
public void push(T v)
{
if (Count >= heap.Length) Array.Resize(ref heap, Count * 2);
heap[Count] = v;
SiftUp(Count++);
}
public T pop()
{
var v = top();
heap[0] = heap[--Count];
if (Count > 0) SiftDown(0);
return v;
}
public T top()
{
if (Count > 0) return heap[0];
throw new InvalidOperationException("优先队列为空");
}
void SiftUp(int n)
{
var v = heap[n];
for (var n2 = n / 2; n > 0 && comparer.Compare(v, heap[n2]) > 0; n = n2, n2 /= 2) heap[n] = heap[n2];
heap[n] = v;
}
void SiftDown(int n)
{
var v = heap[n];
for (var n2 = n * 2; n2 < Count; n = n2, n2 *= 2)
{
if (n2 + 1 < Count && comparer.Compare(heap[n2 + 1], heap[n2]) > 0) n2++;
if (comparer.Compare(v, heap[n2]) >= 0) break;
heap[n] = heap[n2];
}
heap[n] = v;
}
}

一件容易的事。

我最近遇到了同样的问题，最终为此创建了NuGet包。

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

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

更多信息可以在github页面上找到。

AlgoKit

我写了一个名为AlgoKit的开源库，可以通过NuGet获得。它包含:

• 隐式d-ary堆 (ArrayHeap),
• 二项堆,
• 配对堆。

代码已经经过了广泛的测试。我强烈建议你试一试。

例子

var comparer = Comparer<int>.Default;
var heap = new PairingHeap<int, string>(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);

为什么有三堆?

实现的最佳选择是强烈依赖于输入的——正如Larkin, Sen和Tarjan在优先队列回归基础的实证研究， arXiv: 1403.0252 v1 [cs。DS)中所示。他们测试了隐式d-ary堆、配对堆、斐波那契堆、二项式堆、显式d-ary堆、排名配对堆、震动堆、违反堆、排名放松的弱堆和严格斐波那契堆。

AlgoKit具有三种类型的堆，在测试中似乎是最有效的。

关于选择的提示

对于数量相对较少的元素，您可能会对使用隐式堆感兴趣，特别是第四元堆(隐式4元)。在操作较大堆大小的情况下，像二项式堆和配对堆这样的平摊结构应该执行得更好。

一个简单的最大堆实现。

https://github.com/bharathkumarms/AlgorithmsMadeEasy/blob/master/AlgorithmsMadeEasy/MaxHeap.cs

using System;
using System.Collections.Generic;
using System.Linq;


namespace AlgorithmsMadeEasy
{
class MaxHeap
{
private static int capacity = 10;
private int size = 0;
int[] items = new int[capacity];


private int getLeftChildIndex(int parentIndex) { return 2 * parentIndex + 1; }
private int getRightChildIndex(int parentIndex) { return 2 * parentIndex + 2; }
private int getParentIndex(int childIndex) { return (childIndex - 1) / 2; }


private int getLeftChild(int parentIndex) { return this.items[getLeftChildIndex(parentIndex)]; }
private int getRightChild(int parentIndex) { return this.items[getRightChildIndex(parentIndex)]; }
private int getParent(int childIndex) { return this.items[getParentIndex(childIndex)]; }


private bool hasLeftChild(int parentIndex) { return getLeftChildIndex(parentIndex) < size; }
private bool hasRightChild(int parentIndex) { return getRightChildIndex(parentIndex) < size; }
private bool hasParent(int childIndex) { return getLeftChildIndex(childIndex) > 0; }


private void swap(int indexOne, int indexTwo)
{
int temp = this.items[indexOne];
this.items[indexOne] = this.items[indexTwo];
this.items[indexTwo] = temp;
}


private void hasEnoughCapacity()
{
if (this.size == capacity)
{
Array.Resize(ref this.items,capacity*2);
capacity *= 2;
}
}


public void Add(int item)
{
this.hasEnoughCapacity();
this.items[size] = item;
this.size++;
heapifyUp();
}


public int Remove()
{
int item = this.items[0];
this.items[0] = this.items[size-1];
this.items[this.size - 1] = 0;
size--;
heapifyDown();
return item;
}


private void heapifyUp()
{
int index = this.size - 1;
while (hasParent(index) && this.items[index] > getParent(index))
{
swap(index, getParentIndex(index));
index = getParentIndex(index);
}
}


private void heapifyDown()
{
int index = 0;
while (hasLeftChild(index))
{
int bigChildIndex = getLeftChildIndex(index);
if (hasRightChild(index) && getLeftChild(index) < getRightChild(index))
{
bigChildIndex = getRightChildIndex(index);
}


if (this.items[bigChildIndex] < this.items[index])
{
break;
}
else
{
swap(bigChildIndex,index);
index = bigChildIndex;
}
}
}
}
}


/*
Calling Code:
MaxHeap mh = new MaxHeap();
mh.Add(10);
mh.Add(5);
mh.Add(2);
mh.Add(1);
mh.Add(50);
int maxVal  = mh.Remove();
int newMaxVal = mh.Remove();
*/

正如@rustyx所评论的，. net 6添加了一个System.Collections.Generic.PriorityQueue< TElement TPriority>类。FWIW是开源的，在c#中实现。

早期的。net核心版本和。net框架:微软已经在。net框架中编写了(并在网上共享)2个内部PriorityQueue类。然而，正如@ mathumum -mut所评论的那样，其中有一个错误(当然，SO社区已经提供了修复):微软内部的PriorityQueue<T>?