c# 中的斐波那契、二进制或二项式堆？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/428829/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fibonacci, Binary, or Binomial heap in c#?
提问by Dave Moore
Are there any heap data structure implementations out there, fibonacci, binary, or binomial?
是否有任何堆数据结构实现，斐波那契、二进制或二项式？
Reference: These are data structures used to implement priority queues, not the ones used to allocate dynamic memory. See http://en.wikipedia.org/wiki/Heap_(data_structure)
参考：这些是用于实现优先级队列的数据结构，而不是用于分配动态内存的数据结构。见http://en.wikipedia.org/wiki/Heap_(data_structure)
Thanks, Dave
谢谢，戴夫
采纳答案by Jakub ?turc
回答by Mitch Wheat
Free C# implementation of heaps and many other data structures:
堆和许多其他数据结构的免费 C# 实现：
回答by Roman Starkov
QuickGraphimplements Fibonacci Heaps and Queues in C#, among a whole lot of other stuff. It is free and open-source.
QuickGraph在 C# 中实现了斐波那契堆和队列，还有很多其他的东西。它是免费和开源的。
回答by nbilal
I believe that a SortedSet<KeyValuePair<K,V>>with a custom Comparerwill do the job.
我相信SortedSet<KeyValuePair<K,V>>有习惯的人Comparer会完成这项工作。
The Comparerwill look like the following:
该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;
}
}
With such Comparer, the SortedSetwill be sorted by Key and it will allow duplicates of keys.
这样Comparer，SortedSet将按 Key 排序，并允许重复键。
You can get the Minat constant time, RemoveMinat O(logn), Addan entry at O(logn)and Updatea key at O(logn).
您可以获得Minat 恒定时间、RemoveMinat O(logn)、Add一个条目 atO(logn)和Update一个键 at O(logn)。
Here is a full (or almost) implementation:
这是一个完整（或几乎）的实现：
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;
}
}
}
回答by Bharathkumar V
A Simple Min Heap Implementation.
一个简单的最小堆实现。
https://github.com/bharathkumarms/AlgorithmsMadeEasy/blob/master/AlgorithmsMadeEasy/MinHeap.cs
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();
*/
回答by justcoding121
Stand alone stress tested implementations are in Github under Advanced-Algorithmsrepository (I own it). DecrementKey operation performance is what makes later two significant.
独立的压力测试实现位于 Github 下的Advanced-Algorithms存储库（我拥有它）。DecrementKey 操作性能是使后面两个重要的原因。
- Binary Min/Max Heap
- Binomial Min/Max Heap
- Fibornacci Min/Max Heap
- 二进制最小/最大堆
- 二项式最小/最大堆
- 斐波那契最小/最大堆
The repository has two more heap implementations, D-Ary Heap & Pairing Heap.
存储库还有两个堆实现，D-Ary Heap 和 Pairing Heap。
回答by Yosef Dinerstein
Implementation of MinHeap and MaxHeap:
MinHeap 和 MaxHeap 的实现：
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)
{
}
}
