c＃中的Fibonacci，Binary或Binomial堆？

Question

有沒有堆數據結構的實現，斐波那契，二進制或二項嗎？

參考：這些是用於實現優先級隊列的數據結構，而不是用於分配動態內存的數據結構。見http://en.wikipedia.org/wiki/Heap_(data_structure)

謝謝， 戴夫

Answer 1

我不知道任何本地框架實​​現的。

我發現二進制堆的兩個實現（link 1,link 2）和f＃中的二項式堆的一個實現（link）。

Answer 2

我實現了一個FibonacciHeap並對其性能表示滿意。這並不難實施。我使用http://www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAlgorithm.html

Answer 3

免費的C＃實現堆和許多其他數據結構的僞代碼：

• The C5 Generic Collection Library for C# and CLI
• Wintellect's Power Collections for .NET

Answer 4

QuickGraph實現斐波那契堆和隊列在C＃中，整間很多其他的東西。它是免費且開源的。

Answer 5

爲Dijkstra算法堆的實現可以在http://vijayt.com/Post/Min-Heap-implementation-for-Dijkstra-algorithm

Answer 6

找到我相信，隨着定製Comparer一個SortedSet<KeyValuePair<K,V>>將做的工作。

的Comparer將如下所示：

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

有了這樣Comparer，則SortedSet將重點進行排序，它將使密鑰的副本。

您可以在O(logn)和Update在O(logn)一鍵獲得Min在固定的時間，RemoveMin在O(logn)，Add的條目。

這是一個完整的（或幾乎）執行：

public class Heap<K, V> 
    where K : IComparable 
    where V : IComparable 
{ 
    private readonly SortedSet<KeyValuePair<K, V>> _sortedSet; 

    // O(1) 
    public KeyValuePair<K, V> Min 
    { 
     get { return _sortedSet.Min; } 
    } 

    public Heap() 
    { 
     _sortedSet = new SortedSet<KeyValuePair<K, V>>(new KeyValueComparer<K, V>()); 
    } 

    // O(logn) 
    public void Add(K key, V value) 
    { 
     _sortedSet.Add(new KeyValuePair<K, V>(key, value)); 
    } 

    // O(logn) 
    public KeyValuePair<K, V> RemoveMin() 
    { 
     var min = Min; 
     _sortedSet.Remove(min); 
     return min; 
    } 

    // O(logn) 
    public void Remove(K key, V value) 
    { 
     _sortedSet.Remove(new KeyValuePair<K, V>(key, value)); 
    } 

    // O(logn) 
    public void UpdateKey(K oldKey, V oldValue, K newKey) 
    { 
     Remove(oldKey, oldValue); 
     Add(newKey, oldValue); 
    } 

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

Answer 7

一個簡單的最小堆實現。

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 8

單機應力測試的實現是在Github的下Advanced-Algorithms庫。遞減鍵操作性能是後面兩個重要的。

• 二進制最小堆（Implementation | Tests）
• 二項式最小堆（Implementation | Tests）
• Fibornacci最小堆（Implementation | Tests）

存儲庫具有兩個更多的堆實現中， D-Ary堆&配對堆。 MinHeap和MaxHeap的

Answer 9

實現：

public abstract class Heap<T> 
{ 
    private List<T> 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<T>(); 
    } 

    public Heap(IEnumerable<T> elements) 
    { 
     m_Vector = new List<T>(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<T> : Heap<T> where T: IComparable 
{ 
    protected override int Compare(T a, T b) 
    { 
     return a.CompareTo(b); 
    } 

    public MinHeap() : base() 
    { 
    } 

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

public class MaxHeap<T> : Heap<T> where T : IComparable 
{ 
    protected override int Compare(T a, T b) 
    { 
     return b.CompareTo(a); 
    } 

    public MaxHeap() : base() 
    { 
    } 

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