我正在寻找优先级队列或堆数据结构的.NET实现
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.
The basic priority queue supports three primary operations:
Insert(Q,x). Given an item x with key k, insert it into the priority queue Q.
Find-Minimum(Q). Return a pointer to the item
whose key value is smaller than any other key in the priority queue
Q.
Delete-Minimum(Q). Remove the item from the priority queue Q whose key is minimum
除非我找错地方了，否则框架里没有。有谁知道好的吗，还是我自己卷?
你可能会喜欢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/安装
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;
}
}
一件容易的事。
一个简单的最大堆实现。
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();
*/
