c# - the - what is heap in programming

Clase de pila en.NET

Question

Posible duplicado:
Fibonacci, Binary, o Binomial montón en c #?

¿Hay alguna clase como montón en .NET? Necesito algún tipo de colección de la que pueda recuperar min. elemento. Solo quiero 3 métodos:

• Añadir()
• RemoveMinElement ()
• GetMinElement ()

No puedo usar la lista ordenada porque las claves deben ser únicas y es posible que tenga varios elementos idénticos.

Answer 1

Las colas de prioridad parecen ser un buen ajuste para su problema: la cola de prioridad en .Net

Google para "colas de prioridad de C #" para más implementaciones.

Answer 2

Puede usar SortedList o SortedDictionary (consulte la discusión a continuación) con una clave personalizada. Si usó un tipo con igualdad referencial, pero podría compararse según el valor que le interesa, esto podría funcionar.

Algo como esto:

class HeapKey : IComparable<HeapKey>
{
public HeapKey(Guid id, Int32 value)
{
Id = id;
Value = value;
}
public Guid Id { get; private set; }
public Int32 Value { get; private set; }
public int CompareTo(HeapKey other)
{
if (_enableCompareCount)
{
++_compareCount;
}
if (other == null)
{
throw new ArgumentNullException("other");
}
var result = Value.CompareTo(other.Value);
return result == 0 ? Id.CompareTo(other.Id) : result;
}
}

Este es un ejemplo práctico del uso de un SortedDictionary que tiene características de rendimiento de pila binaria:

using System;
using System.Collections.Generic;
using System.Linq;
namespace SortedDictionaryAsBinaryHeap
{
class Program
{
private static Boolean _enableCompareCount = false;
private static Int32 _compareCount = 0;
static void Main(string[] args)
{
var rnd = new Random();
for (int elementCount = 2; elementCount <= 6; elementCount++)
{
var keyValues = Enumerable.Range(0, (Int32)Math.Pow(10, elementCount))
.Select(i => new HeapKey(Guid.NewGuid(), rnd.Next(0, 10)))
.ToDictionary(k => k);
var heap = new SortedDictionary<HeapKey, HeapKey>(keyValues);
_compareCount = 0;
_enableCompareCount = true;
var min = heap.First().Key;
_enableCompareCount = false;
Console.WriteLine("Element count: {0}; Compare count for getMinElement: {1}",
(Int32)Math.Pow(10, elementCount),
_compareCount);
_compareCount = 0;
_enableCompareCount = true;
heap.Remove(min);
_enableCompareCount = false;
Console.WriteLine("Element count: {0}; Compare count for deleteMinElement: {1}",
(Int32)Math.Pow(10, elementCount),
_compareCount);
}
Console.ReadKey();
}
private class HeapKey : IComparable<HeapKey>
{
public HeapKey(Guid id, Int32 value)
{
Id = id;
Value = value;
}
public Guid Id { get; private set; }
public Int32 Value { get; private set; }
public int CompareTo(HeapKey other)
{
if (_enableCompareCount)
{
++_compareCount;
}
if (other == null)
{
throw new ArgumentNullException("other");
}
var result = Value.CompareTo(other.Value);
return result == 0 ? Id.CompareTo(other.Id) : result;
}
}
}
}

Resultados:

Recuento de elementos: 100; Compare la cuenta para getMinElement: 0

Recuento de elementos: 100; Compare la cuenta para deleteMinElement: 8

Recuento de elementos: 1000; Compare la cuenta para getMinElement: 0

Recuento de elementos: 1000; Compare la cuenta para deleteMinElement: 10

Cantidad de elementos: 10000; Compare la cuenta para getMinElement: 0

Cantidad de elementos: 10000; Compare la cuenta para deleteMinElement: 13

Cantidad de elementos: 100000; Compare la cuenta para getMinElement: 0

Cantidad de elementos: 100000; Compare la cuenta para deleteMinElement: 14

Recuento de elementos: 1000000; Compare la cuenta para getMinElement: 0

Recuento de elementos: 1000000; Compare la cuenta para deleteMinElement: 21