c＃中的Fibonacci，Binary或Binomial堆？

是否存在任何堆数据结构实现，斐波那契，二进制或二项式？

参考：这些是用于实现优先级队列的数据结构，而不是用于分配动态内存的数据结构。 见http://en.wikipedia.org/wiki/Heap_(data_structure）

谢谢，戴夫

Answer 1

我不知道任何本机框架实现。

我发现了二进制堆的两个实现（ 链接1 ， 链接2 ）和f＃（ 链接 ）中的二项堆的一个实现。

Answer 2

免费C＃实现堆和许多其他数据结构：

• C＃和CLI的C5通用集合库
• Wintellect的.NET电源系列

Answer 3

QuickGraph在C＃中实现了斐波纳契堆和队列，还包括很多其他东西。 它是免费和开源的。

Answer 4

独立的压力测试实现在Advanced-Algorithms存储库的Github中。 DecrementKey操作性能是后来两个重要的。

• 二进制最小/最大堆
• 二项式最小/最大堆
• Fibornacci最小/最大堆

存储库还有两个堆实现，即D-Ary堆和配对堆。

Answer 5

我相信带有自定义Comparer的SortedSet>将完成这项工作。

Comparer将如下所示：

 class KeyValueComparer : IComparer> where K:IComparable where V:IComparable { public int Compare(KeyValuePair x, KeyValuePair y) { var res = x.Key.CompareTo(y.Key); return res == 0 ? x.Value.CompareTo(y.Value) : res; } } 

使用这样的Comparer ， SortedSet将按键排序，它将允许重复键。

您可以在常量时间获取Min ，在O(logn)处获取RemoveMin在O(logn) Add条目并在O(logn) Update密钥。

这是一个完整的（或几乎）实现：

 public class Heap where K : IComparable where V : IComparable { private readonly SortedSet> _sortedSet; // O(1) public KeyValuePair Min { get { return _sortedSet.Min; } } public Heap() { _sortedSet = new SortedSet>(new KeyValueComparer()); } // O(logn) public void Add(K key, V value) { _sortedSet.Add(new KeyValuePair(key, value)); } // O(logn) public KeyValuePair RemoveMin() { var min = Min; _sortedSet.Remove(min); return min; } // O(logn) public void Remove(K key, V value) { _sortedSet.Remove(new KeyValuePair(key, value)); } // O(logn) public void UpdateKey(K oldKey, V oldValue, K newKey) { Remove(oldKey, oldValue); Add(newKey, oldValue); } private class KeyValueComparer : IComparer> where K : IComparable where V : IComparable { public int Compare(KeyValuePair x, KeyValuePair y) { var res = x.Key.CompareTo(y.Key); return res == 0 ? x.Value.CompareTo(y.Value) : res; } } } 

Answer 6

我实施了FibonacciHeap，并对其性能表示满意。 它并不难实现。 我使用了来自http://www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAlgorithm.html的伪代码

Answer 7

可以在http://vijayt.com/Post/Min-Heap-implementation-for-Dijkstra- algorithm中找到Dijkstra算法的堆实现。

Answer 8

简单的最小堆实现。

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

 using System; using System.Collections.Generic; using System.Linq; namespace AlgorithmsMadeEasy { public class MinHeap { 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 bool hasLeftChild(int index) { return getLeftChildIndex(index) < size; } private bool hasRightChild(int index) { return getRightChildIndex(index) < this.size; } private bool hasParent(int index) { return getParentIndex(index) >= 0; } private int leftChild(int index) { return this.items[getLeftChildIndex(index)]; } private int rightChild(int index) { return this.items[getRightChildIndex(index)]; } private int parent(int index) { return this.items[this.getParentIndex(index)]; } private void swap(int indexOne, int indexTwo) { int temp = this.items[indexOne]; this.items[indexOne] = this.items[indexTwo]; this.items[indexTwo] = temp; } private void ensureExtraCapacity() { if (this.size == capacity) { Array.Resize(ref this.items, capacity*2); capacity *= 2; } } public int peek() { if(this.size==0) throw new NotSupportedException(); return this.items[0]; } public int remove() { if(this.size==0) throw new NotSupportedException(); int item = this.items[0]; items[0] = items[this.size - 1]; items[this.size - 1] = 0; this.size--; heapifyDown(); return item; } public void Add(int item) { this.ensureExtraCapacity(); this.items[size] = item; this.size++; heapifyUp(); } private void heapifyUp() { int index = this.size - 1; while (hasParent(index) && parent(index) > this.items[index]) { swap(index,getParentIndex(index)); index = getParentIndex(index); } } private void heapifyDown() { int index = 0; while (hasLeftChild(index)) { int smallerChildIndex = getLeftChildIndex(index); if (hasRightChild(index) && rightChild(index) < leftChild(index)) { smallerChildIndex = getRightChildIndex(index); } if (this.items[index] < this.items[smallerChildIndex]) { break; } else { swap(index,smallerChildIndex); } index = smallerChildIndex; } } } } /* Calling Code: MinHeap mh = new MinHeap(); mh.Add(10); mh.Add(5); mh.Add(2); mh.Add(1); mh.Add(50); int peek = mh.peek(); mh.remove(); int newPeek = mh.peek(); */ 

Answer 9

MinHeap和MaxHeap的实现：

 public abstract class Heap { private List m_Vector; private void Swap(int i, int j) { var tmp = m_Vector[i]; m_Vector[i] = m_Vector[j]; m_Vector[j] = tmp; } protected abstract int Compare(T a, T b); private void SiftUp(int i) { if (i == 0) { return; } int parent = (i - 1) / 2; if (Compare(m_Vector[i], m_Vector[parent]) >= 0) { return; } Swap(i, parent); SiftUp(parent); } private void SiftDown(int i) { int left = i * 2 + 1; if (left >= m_Vector.Count) { return; } var right = left + 1; var child = left; if (right < m_Vector.Count) { if (Compare(m_Vector[left], m_Vector[right]) > 0) { child = right; } } if (Compare(m_Vector[i], m_Vector[child]) <= 0) { return; } Swap(i, child); SiftDown(child); } public Heap() { m_Vector = new List(); } public Heap(IEnumerable elements) { m_Vector = new List(elements); if (m_Vector.Count < 2) { return; } // // From the last parent, upwards, sift down. Each sift is O<1>. // for (int i = (m_Vector.Count - 2) / 2; i >= 0; i--) { SiftDown(i); } } public int Count { get { return m_Vector.Count; } } public void Add(T element) { m_Vector.Add(element); SiftUp(m_Vector.Count - 1); } public T Top { get { if (m_Vector.Count == 0) { throw new InvalidOperationException(); } return m_Vector[0]; } } public T Fetch() { if (m_Vector.Count == 0) { throw new InvalidOperationException(); } T result = m_Vector[0]; m_Vector[0] = m_Vector[m_Vector.Count - 1]; m_Vector.RemoveAt(m_Vector.Count - 1); SiftDown(0); return result; } } public class MinHeap : Heap where T: IComparable { protected override int Compare(T a, T b) { return a.CompareTo(b); } public MinHeap() : base() { } public MinHeap(IEnumerable elements) : base(elements) { } } public class MaxHeap : Heap where T : IComparable { protected override int Compare(T a, T b) { return b.CompareTo(a); } public MaxHeap() : base() { } public MaxHeap(IEnumerable elements) : base(elements) { } }