Gibt es irgendwelche Heap-Datenstruktur-Implementierungen da draußen, Fibonacci, Binär oder Binomial?Fibonacci, Binary oder Binomial Heap in C#?
Referenz: Dies sind Datenstrukturen, die zum Implementieren von Prioritätswarteschlangen verwendet werden und nicht zum Zuweisen von dynamischem Speicher. Siehe http://en.wikipedia.org/wiki/Heap_(data_structure)
Danke, Dave
Ich implementierte einen FibonacciHeap und war mit seiner Leistung zufrieden. Es ist nicht so schwer zu implementieren. Ich benutzte die Pseudo-Code von http://www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAlgorithm.html
Kostenlose C# -Implementierung von Halden und viele andere Datenstrukturen:
QuickGraph implementiert Fibonacci Heaps und Warteschlangen in C# unter einer ganzen Viele andere Sachen. Es ist kostenlos und Open-Source.
Dokumentation für QuickGraph ist schwierig zu analysieren, wenn Sie nur nach einem Fib-Heap suchen. Quellcode ist auch nicht sehr klar. :( – MushinNoShin
Eine Implementierung von Heap für Dijkstra-Algorithmus kann ich in http://vijayt.com/Post/Min-Heap-implementation-for-Dijkstra-algorithm
zu finden glauben, dass ein SortedSet<KeyValuePair<K,V>> mit einem benutzerdefinierten Comparer den Job tun.
Die Comparer wird wie folgt aussehen:
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;
}
}
Mit einer solchen Comparer wird die SortedSet von Key sortiert werden und es wird Nachschlüssel ermöglichen.
Sie können die Min bei konstanter Zeit bekommen, RemoveMin bei O(logn), Add ein Eintrag bei O(logn) und Update ein Schlüssel bei O(logn).
ist hier eine voll (oder fast) Umsetzung:
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;
}
}
}
A Simple Min Heap-Implementierung.
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();
*/
Stand alone Stress getestet Implementierungen sind in Github unter Advanced-Algorithms Repository. DecrementKey-Betriebsleistung ist, was später zwei bedeutende macht.
Das Repository zwei weitere Heap-Implementierungen hat, D-Ary Heap & Paarung Heap.
Implementierung von MinHeap und 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)
{
}
}
Einfach nur neugierig, was Sie für einen Haufen schreiben? – core
http://stackoverflow.com/a/13776636/67824 –
Siehe auch https://stackoverflow.com/questions/102398/priority-queue-in-net –