programacion - Hexagonal de Fibonacci, Binario o Binomial en c#?
coeficientes binomiales programacion dinamica (9)
¿Hay implementaciones de estructura de datos de montón por ahí, fibonacci, binario o binomial?
Referencia: son estructuras de datos utilizadas para implementar colas de prioridad, no las que se usan para asignar memoria dinámica. Ver http://en.wikipedia.org/wiki/Heap_(data_structure)
Gracias, Dave
Creo que SortedSet<KeyValuePair<K,V>> con un Comparer personalizado hará el trabajo.
Comparer se verá así:
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;
}
}
Con tal Comparer , SortedSet se ordenará por clave y permitirá duplicados de claves.
Puede obtener el Min en tiempo constante, RemoveMin at O(logn) , Add una entrada en O(logn) y Update una clave en O(logn) .
Aquí hay una implementación completa (o casi):
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;
}
}
}
Implementé FibonacciHeap y estaba satisfecho con su rendimiento. No es tan difícil de implementar. Utilicé el pseudocódigo de http://www.cse.yorku.ca/~aaw/Jason/FibonacciHeapAlgorithm.html
Implementación gratuita de C # de montones y muchas otras estructuras de datos:
QuickGraph implementa Fibonacci Heaps and Queues en C #, entre muchas otras cosas. Es gratis y de código abierto.
Se puede encontrar una implementación de heap para el algoritmo Dijkstra en http://vijayt.com/Post/Min-Heap-implementation-for-Dijkstra-algorithm
Una implementación 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();
*/
Implementación de MinHeap y 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)
{
}
}
Las implementaciones autónomas de estrés están en Github en el repositorio de Algoritmos Avanzados . El rendimiento de la operación DecrementKey es lo que hace que los dos últimos sean significativos.
- Binary Minimum Heap ( Implementación | Pruebas )
- Binomial Minimum Heap ( Implementación | Pruebas )
- Fibornacci Minimum Heap ( Implementación | Pruebas )
El repositorio tiene otras dos implementaciones de montón, D-Ary Heap & Pairing Heap.