Existe-t-il des implémentations de structure de données de segment, fibonacci, binaire ou binomiale?Fibonacci, binaire ou tas binomial dans C#?
Référence: Il s'agit de structures de données utilisées pour implémenter des files d'attente de priorité, pas celles utilisées pour allouer de la mémoire dynamique. Voir http://en.wikipedia.org/wiki/Heap_(data_structure)
Merci, Dave
J'ai implémenté un FibonacciHeap et j'étais satisfait de ses performances. Ce n'est pas si difficile à mettre en œuvre. J'ai utilisé le pseudo-code de http://www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAlgorithm.html
mise en œuvre gratuite C# des tas et beaucoup d'autres structures de données:
QuickGraph met en œuvre de Fibonacci Heaps et Queues en C#, parmi l'ensemble beaucoup d'autres choses. C'est gratuit et open-source.
La documentation de QuickGraph est difficile à analyser si vous recherchez un tas de fib. Le code source n'est pas très clair. :( – MushinNoShin
Une implémentation de tas pour l'algorithme Dijkstra se trouve dans http://vijayt.com/Post/Min-Heap-implementation-for-Dijkstra-algorithm
Je crois qu'un SortedSet<KeyValuePair<K,V>> avec une coutume Comparer fera le travail.
Le Comparer se présente comme suit:
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;
}
}
Avec une telle Comparer, le SortedSet seront triés par clé et permettra des doublons de clés.
Vous pouvez obtenir le Min à temps constant, RemoveMin à O(logn), Add une entrée à O(logn) et Update une clé à O(logn).
Voici une complète (ou presque) la mise en œuvre:
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;
}
}
}
Une mise en œuvre simple Min Heap.
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();
*/
le stress de stand seul mises en œuvre sont testées dans Github sous dépôt Advanced-Algorithms. La performance de l'opération DecrementKey est ce qui rend les deux dernières significatives.
Le référentiel a deux implémentations de tas, D-Ary Heap & Jumelage de tas.
mise en œuvre de MinHeap et 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)
{
}
}
Juste curieux, qu'est-ce que vous écrivez un tas pour? – core
http://stackoverflow.com/a/13776636/67824 –
Voir aussi https://stackoverflow.com/questions/102398/priority-queue-in-net –