Существуют ли какие-либо реализации структуры данных кучи, фибоначчи, двоичные или биномиальные?
Ссылка: это структуры данных, используемые для реализации очередей приоритетов, а не те, которые используются для распределения динамической памяти. См. http://en.wikipedia.org/wiki/Heap_(data_structure)
Спасибо, Dave
Я не знаю какой-либо встроенной реализации фреймворка.
Я нашел две реализации двоичной кучи (ссылка 1, ссылка 2) и одна реализация биномиальной кучи в f # (ссылка).
Свободная реализация С# кучи и многих других структур данных:
QuickGraph реализует кучи и очереди Fibonacci на С#, среди всего остального. Он бесплатный и с открытым исходным кодом.
Автономные стресс-тестированные реализации находятся в Github в репозитории Advanced-Algorithms (он мне принадлежит). Выполнение операции DecrementKey - это то, что делает два последующих значимыми.
В репозитории есть еще две реализации кучи, D-Ary Heap и Pairing Heap.
Я считаю, что SortedSet<KeyValuePair<K,V>> с пользовательским Comparer выполнит задание.
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 будет сортироваться по ключу, и он позволит дублировать ключи.
Вы можете получить Min в постоянное время, RemoveMin в O(logn), Add запись в O(logn) и Update клавишу в O(logn).
Вот полная (или почти) реализация:
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;
}
}
}
Я реализовал FibonacciHeap и был доволен своей производительностью. Его не так сложно реализовать. Я использовал псевдокод из http://www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAlgorithm.html
Реализация кучи для алгоритма Дейкстры можно найти в http://vijayt.com/Post/Min-Heap-implementation-for-Dijkstra-algorithm
Простая реализация минимальной кучи.
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();
*/
Реализация 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)
{
}
}